本文主要是介绍排序类算法阶段性总结，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
1.快速排序
/** 快速排序* 不稳定：在一个待排序队列中,A和B相等,且A排在B的前面,而排序之后,A排在了B的后面.这个时候,我们说这种算法是不稳定的.* */public void fastSort(int a[], int start, int end) {if (start >= end) return;int i = start, j = end;boolean flag = true;while (i < j) {if (a[i] > a[j]) {swap(a, i, j);flag = !flag;}if (flag) j--;else i++;}fastSort(a, start, i - 1);fastSort(a, i + 1, end);}public void swap(int a[], int i, int j) {int tmp = a[j];a[j] = a[i];a[i] = tmp;}时间复杂度：最好O(nlogn),最坏O(n^2)
2.堆排序
//堆排序public void heapSort(int a[]) {int n = a.length;for (int i = n / 2 - 1; i >= 0; i--) {heapAjust(a, i, n);}for (int i = n - 1; i > 0; i--) {swap(a, 0, i);heapAjust(a, 0, i);}}private void heapAjust(int[] a, int i, int n) {int left = 2 * i + 1;while (left < n) {int right = left + 1;if (right < n && a[left] < a[right]) {left = right;}if (a[i] < a[left]) {swap(a, i, left);i = left;left = 2 * i + 1;} else {break;}}}@Testpublic void test22() {int a[] = {5, 7, 8, 9, 3, 1, 4, 2, 10, 6, 11};heapSort(a);for (int elem : a) {System.out.print(elem + "\t");}} /** 堆排序类题目* 堆排序原理：以大顶堆为例* 1.输出堆顶元素后，调整剩余元素成为新堆：输出堆顶元素后，以堆中最后一个元素代替，这时根节点的左右子树都是大顶堆，需自上而下进行调整，不断比较左右孩子，取最大的那个交换。交换后继续以这样的方式调整* 2.将无序序列构建成一个堆：将序列看成一个完全二叉树。最后一个非终端结点的坐标是（n-2）/2.从最后一个非终端结点开始自上而下调整，然后在调整倒数第二个，直到第一个结点调整完，便建立了初始堆。* * * 题目描述：找到倒数第 k 个的元素。(找第k大的元素)* 思路1：维护一个k个数量的小顶堆，堆顶元素相当于界限,它是堆中所有元素的最小值。* 遍历所有元素，如果比它大，则把它替换掉 ,所以堆中存储的是目前为止k个最大的元素。* 思路2:利用快排的原理做* */public int findKthLargest(int[] nums, int k) {PriorityQueue<Integer> minHeap = new PriorityQueue<>();//小顶堆for (int val : nums) {minHeap.add(val);if (minHeap.size() > k) minHeap.poll();}return minHeap.peek();}时间复杂度：O(nlogn)
3.桶排序
/** 桶排序* 原理：第i个桶中存放的是频率为i的元素们.* 题目：出现频率最多的 k 个元素* 相似思路题目：按照字符出现次数对字符串排序* */public List<Integer> topKFrequent(int[] nums, int k) {HashMap<Integer, Integer> countOfnum = new HashMap<>();for (int num : nums) {countOfnum.put(num, countOfnum.getOrDefault(num, 0) + 1);}List<Integer>[] buckets = new ArrayList[nums.length + 1];for (int key : countOfnum.keySet()) {int value = countOfnum.get(key);//buckets[value]if (buckets[value] == null) buckets[value] = new ArrayList<>();buckets[value].add(key);}List<Integer> topKFrequent = new LinkedList<>();for (int i = buckets.length - 1; i >= 0; i--) {List<Integer> elems = buckets[i];if (elems != null) {Iterator<Integer> elemIt = elems.iterator();while (elemIt.hasNext()) {topKFrequent.add(elemIt.next());if (topKFrequent.size() == k) return topKFrequent;}}}return topKFrequent;}
时间复杂度O(n)
4.归并排序
/** 归并排序* 思路：将数组均分成两份，将每一份排好序，再将两份有序序列合并。递归这个过程。* 对两个有序序列合并，时间复杂度可以为O(n)* 可以用归并排序的思路解决逆序对的问题* */public void mergeSort(int a[]) {int[] cache = new int[a.length];sort(a, 0, a.length - 1, cache);}private void sort(int[] a, int start, int end, int[] cache) {if (start == end) {return;}int mid = (start + end) / 2;sort(a, start, mid, cache);sort(a, mid + 1, end, cache);merge(a, start, mid, end, cache);}private void merge(int[] a, int start, int mid, int end, int cache[]) {int i = start;int j = mid + 1;int k = 0;while (i <= mid && j <= end) {if (a[i] > a[j]) {cache[k++] = a[j++];} else {cache[k++] = a[i++];}}if (i <= mid) while (i <= mid) cache[k++] = a[i++];if (j <= end) while (j <= end) cache[k++] = a[j++];for (int p = 0; p < k; p++) a[start++] = cache[p];}
时间复杂度O(nlogn)
5.荷兰国旗问题：
/** 荷兰国旗问题* i每找到一个小于flag的数，就和left交换，然后left++* i每找到一个大于flag的数，就和right交换，然后right--* 大于的放后面，小于的放前面，等于的自然就放在中间了；* */public void sortColors(int[] nums) {int length=nums.length;int i=0,left=0,right=length-1;int flag=1;while (i<=right){if(nums[i]<flag){swap(nums,i,left);i++;left++;}else if(nums[i]>flag){swap(nums,i,right);right--;//这里不可以i++，因为还要比较交换后的元素}else{i++;}}}
时间复杂度O(n)
这篇关于排序类算法阶段性总结的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
