Loading... ## 十种经典排序算法 [排序算法动画](https://www.cs.usfca.edu/~galles/visualization/Algorithms.html) 以下排序代码中的 swap 方法为该方法， ```java // 将下标为i ,i+1 位置的值进行互换 public void swap(int[] arr,int i,int j){ int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } ``` ### 1. 冒泡排序（稳定） #### 1).原理 - a. 比较相邻的元素，如果第一个比第二个大，就交换他们两个； - b. 对每一对相邻的元素做同样的工作，从开始到最后的一对，最后一个元素为最大的数； - c. 除去最后一个元素，针对所有元素重复以上步骤； - d. 持续对每次越来越少的元素重复上面的步骤，直达没有一对数字需要比较。 -  #### 2). code ```java for(int i = arr.length - 1;i > 0; i--){ for(int j = 0;j < i;j++){ if(arr[i] > arr[i+1}){ swap(arr,i.i+1) } } } ``` #### 3). 时间复杂度 - 平均时间复杂度：O(n²) - 最好情况O(n) - 最坏情况O(n²） ### 2. 选择排序（不稳定） #### 1). 原理 - a. 从第二个元素开始，后一个元素和前一个元素进行对比，后面的小，则交换； - b. 对每一对相邻的元素做同样的工作，这样一轮之后，最小的元素在第一个； - c. 除去第一个，进行第二轮，将最小的元素下标与最小元素的下一个进行交换； - d. 持续对每次越来越少的元素重复上面的步骤，直达没有一对数字需要比较。  #### 2). code ```java for(int i = 0; i < arr.length - 1;i++){ int minIndex = i; for(int j = i + 1;j < arr.length;j++){ //每次与找到的最小值比较，如果找到更小的，最小值下标交换 minIndex = arr[j] < arr[minIndex] ? j : minIndex; } //将最小值换到i 位置 swap(arr,i,minIndex); } ``` #### 3). 时间复杂度 * 平均时间复杂度：O(n²) * 最好情况O(**n²**) * 最坏情况O(****n²****） ### 3. 插入排序（稳定） #### 1). 原理 * a. 要排序的值向有序的序列中插值 * b. 与排好序的最后一个值进行比较，如果当前值比较小，交换， * c. 再与交换后的前一个值比较，如果小交换，否则不交换，排序成功 - -  #### 2). code ```java for(int i = 1;i < arr.length - 1;i++){ for(int j = i - 1;j >= 0 && arr[j] > arr[j+1];j--){ swap(arr,j,j+1); } } ``` #### 3). 时间复杂度 - 平均时间复杂度O(n²) - 最坏情况O(n²) - 最好情况O(n ### 4. 希尔排序（不稳定） #### 1). 原理 a. 先取一个小于n的整数gap=length/2作为第一个增量 b. 把文件的全部记录分组。所有距离为gap的倍数的记录放在同一个组中。先在各组内进行直接插入排序； c. 缩小增量继续以gap = gap/2的方式，重复bc  #### 2). code ```java private static void shellSort(int[] arr) { //不断缩小增量 int min; int minValue; for (int gap = arr.length / 2; gap > 0; gap /= 2) { for (int i = gap; i < arr.length; i++) { min = i; minValue = arr[i]; while (min >= gap && minValue < arr[min - gap]) { arr[min] = arr[min - gap]; min -= gap; } arr[min] = minValue; } } System.out.println(Arrays.toString(arr)); } ``` #### 3). 时间复杂度 - 平均时间复杂度O(n1.5) - 最坏情况O(n²) ### 5. 归并排序（稳定） #### 1). 原理 - a. 让左右两部分的元素先有序，然后将两个有序的部分合并成一个有序的数组 - b. 继续把左边的部分分为两部分，让左边的部分的两部分有序 - c. 继续把右边的部分分为两部分，让右边的部分的两部分有序 ####  #### 2). code ```java public static void mergeSort(int[] arr) { if (arr == null || arr.length < 2) { return; } mergeSort(arr, 0, arr.length - 1); } public static void mergeSort(int[] arr, int l, int r) { if (l == r) { return; } int mid = l + ((r - l) >> 1); mergeSort(arr, l, mid); mergeSort(arr, mid + 1, r); /*让左右两部分的元素先有序，然后将两个有序的部分合并成一个有序的数组 那怎么让左边的部分和右边的部分有序？ 继续把左边的部分分为两部分，让左边的部分的两部分有序 继续把右边的部分分为两部分，让右边的部分的两部分有序 */ merge(arr, l, mid, r); } public static void merge(int[] arr, int l, int m, int r) { int[] help = new int[r - l + 1]; int i = 0; int p1 = l; int p2 = m + 1; //比较左右两部分的元素，哪个小，把那个元素填入help中 while (p1 <= m && p2 <= r) { help[i++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++]; } //上面的循环退出后，把剩余的元素依次填入到help中 //以下两个while只有一个会执行 while (p1 <= m) { help[i++] = arr[p1++]; } while (p2 <= r) { help[i++] = arr[p2++]; } //把最终的结果复制给原数组 for (i = 0; i < help.length; i++) { arr[l + i] = help[i]; } } ``` ### 6. 快速排序（不稳定） #### 基本思想 通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。 #### 排序流程 a. 先从数组中取出一个基准数 b. 分区，将比基准数大的放在右边，小的放在左边 c. 在对左右部分进行重复第二步，直到只剩一个数  #### 代码实现 ```java public static void quickSort(int[] arr, int p, int r) { if (p < r) { //int q = partition1(arr, p, r); int q = partition2(arr, p, r); quickSort(arr, p, q - 1); quickSort(arr, q + 1, r); } } /** * 方法一：单向扫描 * @param arr * @param p * @param r * @return */ private static int partition1(int[] arr, int p, int r) { int pivot = arr[p];//以数组最左侧的值为目标值 int sp = p + 1; //扫描指针 int bigger = r; //右侧指针 while (sp <= bigger) { if (arr[sp] <= pivot) { //扫描元素小于主元，左指针右移 sp++; } else { //扫描元素大于主元，二指针元素交换，右指针左移 swap(arr, sp, bigger); bigger--; } } swap(arr, p, bigger); return bigger; } /** * 方法二：双向扫描 * @param arr * @param p * @param r * @return */ public static int partition2(int[] arr,int p,int r){ int pivot = arr[p];以数组最左侧的值为目标值 int left = p + 1; //扫描指针 int right = r; //右侧指针 while (left <= right){ //left不停的往右走，知道遇到大于主元的元素 while (left <= right&& arr[left] <= pivot) left++;//循环退出时，left一定指向第一个大于主元的元素 while (left <= right&& pivot < arr[right]) right--;//循环退出时，right一定指向第一个小于主元的元素 if(left<=right){ swap(arr,left,right); } } //while退出时，两者交错，right一定指向第一个小于主元的元素 swap(arr, p, right); return right; } ``` **优化快速排序**，上述两种方法，每次只搞定一个数，而我们进行优化，优化后，可以将所有等于这个数的都搞定，时间复杂度虽然差不多，但是常数项肯定会变小。 ```java public static void quickSort(int[] arr,int p,int r){ if(p < r){ int[] q = partition3(arr,p,r); quickSort(arr,l,q[0] - 1); quickSort(arr,q[1] + 1,r); } } /** * 方法三：优化快速排序 * 将所有等于目标值的独立出来，大于目标值的和小于目标值的继续递归 * @param arr * @param p * @param r * @return */ private static int[] partition3(int[] arr, int p, int r) { int pivot = arr[r]; //以数组最右侧的值为目标值 int less = p - 1; //小于区域的指针 int more = r; //大于区域的指针 int cur = p; while (cur < more){ if(arr[cur] < pivot){ //当前值小于目标值 less ++; //小于区域指针右移 swap(arr,less,cur); cur ++; }else if (arr[cur] > pivot){ //当前值大于目标值 more --; //大于区域指针右移 swap(arr,more,cur); }else { cur ++; } } swap(arr,more,r); //more此时为第一个大于目标值的坐标 // 返回存储等于目标值区域的左边界和右边界的数组 return new int[]{less + 1,more}; } ``` #### 性能分析： 快速排序的一次划分算法从两头交替搜索，直到low和high重合，因此其时间复杂度是O(n)；而整个快速排序算法的时间复杂度与划分的趟数有关。 **理想的情况是**，每次划分所选择的中间数恰好将当前序列几乎等分，经过log2n趟划分，便可得到长度为1的子表。这样，整个算法的时间复杂度为O(nlog2n)。 **最坏的情况是**，每次所选的中间数是当前序列中的最大或最小元素，这使得每次划分所得的子表中一个为空表，另一子表的长度为原表的长度-1。这样，长度为n的数据表的快速排序需要经过n趟划分，使得整个排序算法的时间复杂度为O(n^2)。 **最佳情况：T(n) = O(nlogn) 最差情况：T(n) = O(n2) 平均情况：T(n) = O(nlogn)** --- #### 算法优化 ##### 1、随机快速排序 为了避免最坏情况的发生，我们可以设置目标值为数组中的随机元素。 ```java public static void quickSort(int[] arr,int p,int r){ if(p < r){ //设置目标值为数组中的随机元素,改善最坏情况下的时间性能 swap(arr,l + (int)(Math.random() * (r - p + 1)),r); int[] p = partition(arr,p,r); quickSort(arr,l,p[0] - 1); quickSort(arr,p[1] + 1,r); } } ``` ##### 2、三点中值法 将数组中最左边，中间，最右边三个值对比，中值作为目标值 ```java public static void quickSort(int[] arr, int p, int r) { if (p < r) { int q = partition4(arr, p, r); quickSort(arr, p, q - 1); quickSort(arr, q + 1, r); } } /** * 三点中值法 * @param arr * @param p * @param r * @return */ public static int partition4(int[] arr,int p,int r){ //优化，在P，r,mid之间，选一个中间值作为主元 int midIndex = p + ((r - p) >> 1); //中间下标 int midValueIndex = -1 ; //中值下标 if(arr[p] <= arr[midIndex]&&arr[p] >= arr[r]){ midValueIndex = p; } else if(arr[r] <= arr[midIndex]&&arr[r] >= arr[p]){ midValueIndex = r; }else { midValueIndex = midIndex; } swap(arr,p,midValueIndex); int pivot = arr[p]; int left = p + 1; //扫描指针 int right = r; //右侧指针 while (left <= right){ //left不停的往右走，知道遇到大于主元的元素 while (left <= right&& arr[left] <= pivot) left++;//循环退出时，left一定指向第一个大于主元的元素 while (left <= right&& pivot < arr[right]) right--;//循环退出时，right一定指向第一个小于主元的元素 if(left<=right){ swap(arr,left,right); } } //while退出时，两者交错，right一定指向第一个小于主元的元素 swap(arr, p, right); return right; } ``` 但是三点中值法还是不能够保证没有最坏情况的发生，如果要完全避免最坏情况，则需要使用绝对中值法。 ##### 3、绝对中值法 通过将待排序数组以5个元素分为一组，取中间值，取到整个数组的各组中间值，再将这些数排序，再取中间值作为主元。因为寻找绝对中值，也会花费时间，所以使用三点中值法居多。 ```java /** * 获取绝对的中值数，O(N)的样子 */ public static int getMedian(int[] arr, int p, int r) { if (arr.length == 1) return arr[p]; int size = r - p + 1;// 数组长度 //每五个元素一组 int groupSize = (size % 5 == 0) ? (size / 5) : (size / 5 + 1); //存储各小组的中值 int medians[] = new int[groupSize]; int indexOfMedians = 0; //对每一组进行插入排序 for (int j = 0; j < groupSize; j++) { //单独处理最后一组，因为最后一组可能不满5个元素 if (j == groupSize - 1) { InsertionSort.sort(arr, p + j * 5, r); // 排序最后一组 medians[indexOfMedians++] = arr[(p + j * 5 + r) / 2]; // 最后一组的中间那个 } else { InsertionSort.sort(arr, p + j * 5, p + j * 5 + 4); // 排序非最后一组的某个组 medians[indexOfMedians++] = arr[p + j * 5 + 2]; // 当前组（排序后）的中间那个 } } return getMedian(medians, 0, medians.length - 1); } ``` ##### 4、待排序列表较短时，用插入排序 当排序列表小于8个时，通过计算发现插入排序比快速排序的性能要好。 ### 7. 堆排（不稳定） #### 定义 堆（英语：heap)是计算机科学中一类特殊的数据结构的统称。堆通常是一个可以被看做一棵树的数组对象。堆总是满足下列性质： - - 堆中某个节点的值总是不大于或不小于其父节点的值； - 堆总是一棵完全二叉树。 将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。 #### 堆排序思路： 首先要知道大根堆和小根堆，数组就是一个堆，每个 i 节点的左右孩子是 2i+1 和 2i+2 有了堆，将其堆化：从n/2-1个元素开始向下修复，将每个节点修复为小（大）根堆  修复完成后，数组具有小（大）根堆的性质 按序输出：小根堆可以对数组逆序排序，每次交换栈顶和末尾元素，对栈顶进行向下修复，这样次小元素又到堆顶了 #### 代码实现（小根堆） ```java public class MinHeap { public static void minHeap(int[] A){ int n = A.length; for(int i = n/2 - 1; i >= 0; i-- ){ minHeapFixDown(A,i,n); } } public static void minHeapFixDown(int[] A, int i, int n) { //找到左右孩子 int left = 2 * i + 1; int right = 2 * i + 2; // 左孩子越界，i 就是叶子节点，返回 if(left >= n){ return; } int min = left; // 右孩子越界，最小值为左孩子 if(right >= n){ min = left; }else { //都没有越界，如果右孩子比左孩子小，那最小值为右孩子 if(A[right] < A[left]){ min = right; } } //如果A[i]比两个孩子小，不用调整 if (A[i] < A[min]) { return; } //否则，那个孩子小，那个和i 交换 swap(A,i,min); //哪个孩子发生了变化，继续递归调整，直到子节点 minHeapFixDown(A,min,n); } /** * 小根堆对数组排序 * @param A */ public static void minHeapSort(int[] A){ //先对A进行堆化 minHeap(A); for(int x = A.length - 1; x > 0 ; x--){ //把堆顶和最后一个元素交换 swap(A,0,x); //缩小堆的范围，对堆顶元素进行向下调整 minHeapFixDown(A,0,x); } } /** * 交换 arr 中 下标 i ，j 元素 */ public static void swap(int[] arr, int i, int j) { int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } /** * 对数组进行遍历输出 * @param arr */ public static void printArray(int[] arr) { if (arr == null) { return; } for (int i = 0; i < arr.length; i++) { System.out.print(arr[i] + " "); } System.out.println(); } public static void main(String[] args) { int[] arr = {35,10,26,1,15,13,28}; minHeapSort(arr); printArray(arr); // 35 28 26 15 13 10 1 } } ``` #### 大根堆 ```java public static void maxHeap(int[] A){ int n = A.length; for (int i = n / 2 - 1;i >=0;i--){ maxHeapFixUp(A,i,n); } } private static void maxHeapFixUp(int[] A, int i, int n) { //找出左右子树 int left = 2 * i + 1; int right = 2 * i + 2; //如果左子树越界，则该节点为叶子节点 if(left >= n){ return; } int max = left; //默认左子树为最大值 //如果右子树越界，则左子树为最大值 if(right >= n){ max = left; }else{ //左右子树都不越界，判断大小 if(A[right] > A[left]){ max = right; } } //如果根节点最大，则返回 if(A[i] > A[max]){ return; } //否则，最大值与 i 交换 swap(A, max, i); //那个子树发生变化，与 i 交换后，继续递归调整，直到叶子节点 maxHeapFixUp(A, max, n); } public static void maxHeapSort(int[] A){ //堆化 maxHeap(A); for(int x = A.length - 1 ; x > 0 ;x--){ //最后一个元素和 根节点交换， swap(A,0,x); //缩小堆的范围,对堆进行向下调整 maxHeapFixUp(A,0,x); } } ``` #### 分析： 时间复杂度： - 堆化：一半的元素修复，修复是单分支的，所以整体堆化为nlogn/2 - 排序：n个元素都要取出，因此调整n次，每次调整修复同上是logn的，整体为nlogn 空间复杂度：不需要开辟辅助空间 ### 8. 计数排序(稳定) #### 1). 原理 - 用辅助数组对数组中出现的数组计数，元素转下标，下标转元素 - 假设元素均大于等于0，依次扫描原数组，将元素值k记录在辅助数组的K位 - 依次扫描辅助数组，如果为1，将其插入到目标数组的空白处 #### 2). 思路 1. 开辟新的空间，空间大小为max(source)-min(source)+1 2. 扫描source，将value作为辅助空间的下标，用辅助空间的该位置元素记录value的个数 如：9 7 5 3 1 ，helper=arr(10) 一次扫描，value为9，将helper[9]++，value为7，将helper[7]++…… 如此这般之后，我们遍历helper，如果该位（index）的值为0，说明index不曾在source中出现 如果该位（index)的值为1，说明index在source中出现了1次，为2自然是出现了2次 历helper就能将source修复为升序排列  #### 3). code ```java public static int[] sort(int[] source) { //找到目标数组中的最大值 int max = Util.maxOf(source); int min = Util.minOf(source); //创建辅助空间,helper 数组中，指针存的source的值，元素 为值的个数 int[] helper = new int[max - min + 1]; //将source数组中的值填到helper 数组中 for (int s : source) { //解决出现负数的情况 helper[s - min]++; } int current = 0; //扫描helper 数组，将数组回填 for (int i = 0; i < helper.length; i++) { while (helper[i] > 0) { source[current++] = i + min; helper[i]--; } } return source; } ``` #### 4). 分析 - 时间复杂度：扫描一次source,扫描一个helper,复杂度为O(n+k) - 空间复杂度：辅助空间k,k=maxOf(source)，O(k) 非原址排序 - 稳定性：相同元素不会出现交叉，非原址都是拷来考去 **计数有缺点，数据密集或者范围小时，适用** ### 9. 桶排序（稳定） #### 1). 原理 桶排序是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。 桶排序 (Bucket sort)的工作的原理：假设输入数据服从均匀分布，将数据分到有限数量的桶里，每个桶再分别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排 #### 2). 思路 1. 人为设置一个BucketSize，作为每个桶所能放置多少个不同数值（例如当BucketSize==5时，该桶可以存放｛1,2,3,4,5｝这几种数字，但是容量不限，即可以存放100个3）； 2. 遍历输入数据，并且把数据一个一个放到对应的桶里去； 3. 对每个不是空的桶进行排序，可以使用其它排序方法，也可以递归使用桶排序； 4. 从不是空的桶里把排好序的数据拼接起来。  #### 3). code ```java /** * 桶排序 * * @param array * @param bucketSize 桶中可以放多少种元素 * @return */ public static ArrayList<Integer> BucketSort(ArrayList<Integer> array, int bucketSize) { if (array == null || array.size() < 2) return array; int max = array.get(0), min = array.get(0); // 找到最大值最小值 for (int i = 0; i < array.size(); i++) { if (array.get(i) > max) max = array.get(i); if (array.get(i) < min) min = array.get(i); } int bucketCount = (max - min) / bucketSize + 1; ArrayList<ArrayList<Integer>> bucketArr = new ArrayList<>(bucketCount); ArrayList<Integer> resultArr = new ArrayList<>(); //构造桶 for (int i = 0; i < bucketCount; i++) { bucketArr.add(new ArrayList<Integer>()); } //往桶里塞元素 for (int i = 0; i < array.size(); i++) { bucketArr.get((array.get(i) - min) / bucketSize).add(array.get(i)); } for (int i = 0; i < bucketCount; i++) { if (bucketSize == 1) { for (int j = 0; j < bucketArr.get(i).size(); j++) resultArr.add(bucketArr.get(i).get(j)); } else { if (bucketCount == 1) bucketSize--; ArrayList<Integer> temp = BucketSort(bucketArr.get(i), bucketSize); for (int j = 0; j < temp.size(); j++) resultArr.add(temp.get(j)); } } return resultArr; } ``` #### 4). 分析 **时间复杂度：** - 最佳情况：T(n) = O(n+k) - 最差情况：T(n) = O(n+k) - 平均情况：T(n) = O(n2) ### 10. 基数排序（稳定） #### 1). 原理 基数排序也是非比较的排序算法，对每一位进行排序，从最低位开始排序，复杂度为O(kn),为数组长度，k为数组中的数的最大的位数； 基数排序是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。有时候有些属性是有优先级顺序的，先按低优先级排序，再按高优先级排序。最后的次序就是高优先级高的在前，高优先级相同的低优先级高的在前。基数排序基于分别排序，分别收集，所以是稳定的。 #### 2). 思路 - 取得数组中的最大数，并取得位数； - arr为原始数组，从最低位开始取每个位组成radix数组； - 对radix进行计数排序（利用计数排序适用于小范围数的特点）；  #### 3). code ```java /** * 基数排序 * @param array * @return */ public static int[] RadixSort(int[] array) { if (array == null || array.length < 2) return array; // 1.先算出最大数的位数； int max = array[0]; for (int i = 1; i < array.length; i++) { max = Math.max(max, array[i]); } int maxDigit = 0; while (max != 0) { max /= 10; maxDigit++; } int mod = 10, div = 1; ArrayList<ArrayList<Integer>> bucketList = new ArrayList<ArrayList<Integer>>(); for(int i = 0; i < 10;i++){ bucketList.add(new ArrayList<Integer>()); } for(int i = 0;i < maxDigit;i++,mod *= 10 ,div *= 10){ for(int j = 0;j < array.length;j++){ int num = (array[j] % mod) / div; bucketList.get(num).add(array[j]); } int index = 0; for(int j = 0;j < bucketList.size();j++){ for(int k = 0;k < bucketList.get(j).size();k++){ array[index++] = bucketList.get(j).get(k); } bucketList.get(j).clear(); } } return array; } ``` #### 4). 分析 **时间复杂度：** - 最佳情况：T(n) = O(n*k) - 最差情况：T(n) = O(n*k) - 平均情况：T(n) = O(n*k) Last modification：August 28th, 2021 at 04:58 pm © 允许规范转载