大佬教程收集整理的这篇文章主要介绍了排序算法，大佬教程大佬觉得挺不错的，现在分享给大家，也给大家做个参考。
1.排序分类
2.时间空间复杂度
图片来自：https://www.cnblogs.com/onepixel/articles/7674659.html
原图的快排的空间复杂度错误
3. 具体实现
tips: 按升序排序
3.1 插入排序
1）直接插入排序
思路：
复杂度
public class InsertSort { private static void insertSort(int[] nums) { for (int i=1; i<nums.length; i++) { int j = i - 1; int cur = nums[i]; while (j >= 0 && nums[j] > cur) { nums[j+1] = nums[j]; j--; } nums[j + 1] = cur; } } }
2）希尔排序
思路：是一种特殊的插入排序，其根据不同的步长更新成最终的有序序列
public class S4_SHellSort { private static void sHellSort(int[] nums) { for (int i=(int)Math.floor(nums.length); i>0; i=(int)Math.floor(i/2)) { insertSort(nums, i); } } private static void insertSort(int[] nums, int len) { for (int i=len; i<nums.length; i++) { int j = i - len; int cur = nums[i]; while (j >= 0 && cur < nums[j]) { nums[j + len] = nums[j]; j = j - len; } nums[j + len] = cur; } } }
3.2 交换排序
1）冒泡排序
思路：在一趟排序中，若[i] < [j]，交换两个元素，否则继续向下走。一趟排序结束后，最大关键字被交换到了最后固定位置。如此反复多趟，直到在某一趟一次交换也不发生，排序结束
复杂度：
public class BubbleSort { private static void bubbleSort(int[] nums) { Boolean flag = true; for (int i=0; flag; i++) { flag = false; // 若未发生交换则已经排好序 for (int j=nums.length-1; j>=1; j--) { if (nums[j] < nums[j-1]) { swap(nums, j, j-1); flag = true; } } } } private static void swap(int[] nums, int i, int j) { int t = nums[i]; nums[i] = nums[j]; nums[j] = t; } }
2）快速排序
思路：根据分割函数，确定分割数字的最终位置，分成左右两侧。左侧 <=【分割数字】，【分割数字】 <= 右侧。递归执行
复杂度：
代码1
public class S2_QuickSort { private static void quickSort(int [] nums, int l, int r) { if (l < r) { int mid = partition(nums, l, r); quickSort(nums, l, mid - 1); quickSort(nums, mid+1, r); } } private static int partition(int[] nums, int l, int r) { int flag = nums[r]; while (l < r) { while (l < r && nums[l] < flag) l++; if (l < r) nums[r--] = nums[l]; while (l < r && nums[r] > flag) r--; if (l < r) nums[l++] = nums[r]; } nums[l] = flag; return l; } }
代码2
public class S2_QuickSort2 { private static void quickSort(int [] nums, int l, int r) { if (l < r) { int mid = partition(nums, l, r); quickSort(nums, l, mid - 1); quickSort(nums, mid+1, r); } } private static int partition(int[] nums, int l, int r) { int flag = nums[r]; int i = l - 1; // i指向的位置是分割左侧的最后一个位置 for (int j=l; j<r; j++) { if (nums[j] < flag) { i = i + 1; swap(nums, i, j); } } swap(nums, i + 1, r); return i + 1; } private static void swap(int[] nums, int i, int j) { int t = nums[i]; nums[i] = nums[j]; nums[j] = t; } }
3.3 选择排序
1）简单选择排序
思路：从头到尾在无序序列找到最小关键字，和无序序列第一个元素进行交换。如此反复，直至排序结束
复杂度：
public class SELEctSort { private static void SELEctSort(int[] nums) { for (int i=0; i<nums.length-1; i++) { int minj = i; for (int j=i; j<nums.length; j++) { if (nums[j] < nums[minj]) minj = j; } int t = nums[i]; nums[i] = nums[minj]; nums[minj] = t; } } }
2）堆排序
思路：
复杂度：
public class HeapSort { private static void heapSort(int[] nums) { int n = nums.length - 1; // 堆化成大根堆 for (int i=n/2; i>=0; i--) { heapify(nums, n, i); // System.out.println(nums[0]); } while (n > 0) { // 排序 选取关键字 swap(nums, 0, n); n--; // 堆化 heapify(nums, n, 0); } } // 建立大根堆 private static void heapify(int[] nums, int n, int i) { int l = 2 * i + 1; int r = 2 * i + 2; int t = i; if (l <= n && nums[l] > nums[t]) t = l; if (r <= n && nums[r] > nums[t]) t = r; if (t != i) { swap(nums, t, i); heapify(nums, n, t); } } private static void swap(int[] nums, int i, int j) { int t = nums[i]; nums[i] = nums[j]; nums[j] = t; } }
3.4 归并排序
1）二路归并排序
思路：递归分割为多个有序数组，后合并为一个有序数组
复杂度：
public class MergeSort { private static void mergeSort(int[] nums, int l, int r) { if (l >= r) return ; int mid = l + r >> 1; mergeSort(nums, l, mid); mergeSort(nums, mid + 1, r); merge(nums, l, mid, r); } private static void merge(int[] nums, int l, int mid, int r) { int[] tmp = new int[r - l + 1]; int i1 = l; int i2 = mid + 1; int idx = 0; while (i1 <= mid && i2 <= r) { if (nums[i1] < nums[i2]) tmp[idx++] = nums[i1++]; else tmp[idx++] = nums[i2++]; } while (i1 <= mid) tmp[idx++] = nums[i1++]; while (i2 <= r) tmp[idx++] = nums[i2++]; for (int j=l, j1=0; j<=r; j++) nums[j] = tmp[j1++]; } }
3.5 基数排序
思路：多关键字排序
3.6 计数排序
思路：
public class CountSort { private static int NMAX = 1000; // 数字最大值 private static void countSort(int[] nums) { int n = nums.length; int[] C = new int[NMAX + 1]; int[] B = new int[n + 1]; for (int i=0; i<n; i++) C[nums[i]]++; for (int i=1; i<=NMAX; i++) C[i] = C[i] + C[i-1]; for (int i=0; i<n; i++) { B[C[nums[i]]] = nums[i]; C[nums[i]]--; } // System.out.println(Arrays.toString(B)); for (int i=1; i<=n; i++) nums[i - 1] = B[i]; } }
参考链接：
https://www.cnblogs.com/onepixel/articles/7674659.html
以上是大佬教程为你收集整理的排序算法全部内容，希望文章能够帮你解决排序算法所遇到的程序开发问题。
如果觉得大佬教程网站内容还不错，欢迎将大佬教程推荐给程序员好友。
本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。