【数据结构】排序

目录

1.前言

2.排序的概念及引用

2.1排序的概念

2.2常见的排序算法

 3.常见排序算法的实现

3.1插入排序

3.1.1基本思想

 3.1.2直接插入排序

 3.1.3希尔排序(缩小增量排序)

3.2选择排序

3.2.1基本思想

3.2.2直接选择排序

3.2.3堆排序

3.3交换排序

3.3.1基本思想

3.3.2冒泡排序

3.3.3快速排序

3.4归并排序

3.4.1基本思想

3.4.2海量数据的排序问题

4.排序算法复杂度及稳定性分析

5.其他非基于比较排序

6.总结

1.前言

我们上一次介绍了堆的相关知识，这次要跟大家介绍七种排序算法基本原理、实现和 java 中的常用排序方法。生活中的排序相信大家都很了解，比如考试后对各科成绩进行排名，热搜板根据热度进行排序等等。

2.排序的概念及引用

2.1排序的概念

稳定性 ：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j] ，且 r[i] 在 r[j] 之前，而在排序后的序列中， r[i] 仍在 r[j 之前，则称这种排序算法是稳定的；否则称为不稳定的。

内部排序：数据元素全部放在内存中的排序。

外部排序：数据元素太多不能同时放在内存中，根据排序过程的要求不断在内外存之间移动数据的排序。

2.2常见的排序算法

 3.常见排序算法的实现

3.1插入排序

3.1.1基本思想

直接插入排序是一种简单的插入排序法，其基本思想是：

把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，得到一个新的有序序列。实际中我们玩扑克牌时，就用了插入排序的思想。

 3.1.2直接插入排序

当插入第i(i>=1)个元素时，前面的array[0],array[1],…,array[i-1]已经排好序，此时用array[i]的排序码与array[i-1],array[i-2],…的排序码顺序进行比较，找到插入位置即将array[i]插入，原来位置上的元素顺序后移。

public class Sort {/*时间复杂度：最好：O(N)   最坏：O(N^2)空间复杂度：O(1)稳定性：稳定*///直接插入排序public static void insertSort(int[] arr){for (int i = 0; i < arr.length; i++) {int temp=arr[i];int j=i-1;for (j=i-1; j >=0; j--) {if(arr[j]>temp){arr[j+1]=arr[j];}else{break;}}arr[j+1]=temp;}}
}

import java.util.Arrays;public class Test {public static void main(String[] args) {int[] arr={10,5,8,23,15};//直接插入排序Sort.insertSort(arr);System.out.print("直接插入排序：");System.out.println(Arrays.toString(arr));}
}

直接插入排序的特性总结:

1. 元素集合越接近有序，直接插入排序算法的时间效率越高

2. 时间复杂度：O(N^2)

3. 空间复杂度：O(1)，它是一种稳定的排序算法

4. 稳定性：稳定

 3.1.3希尔排序(缩小增量排序)

public class Sort {/*稳定性：不稳定*///希尔排序public static void shellSort(int[] arr){int gap = arr.length;while(gap>1){gap/=2;shell(arr,gap);}}//每组进行插入排序private static void shell(int[] arr,int gap){//i++ 交替变量进行排序for (int i = gap; i <arr.length ; i++) {int temp=arr[i];int j=i-gap;for (j=i-gap; j>=0; j-=gap) {if(arr[j]>temp){arr[j+gap]=arr[j];}else{break;}}arr[j+gap]=temp;}}
}

import java.util.Arrays;public class Test {public static void main(String[] args) {//希尔排序int[] arr1={8,2,12,6,11};Sort.shellSort(arr1);System.out.print("希尔排序：");System.out.println(Arrays.toString(arr1));}
}

希尔排序的特性总结：

1. 希尔排序是对直接插入排序的优化。

2. 当gap > 1时都是预排序，目的是让数组更接近于有序。当gap == 1时，数组已经接近有序的了，这样就会很快。这样整体而言，可以达到优化的效果。我们实现后可以进行性能测试的对比。

《数据结构-用面向对象方法与C++描述》--- 殷人昆 

所以我们暂时就按照 O(n^1.25)到O(1.6 * n ^ 1.25)来算。

3.2选择排序

3.2.1基本思想

3.2.2直接选择排序

• 在元素集合array[i]--array[n-1]中选择关键码最大(小)的数据元素
• 若它不是这组元素中的最后一个(第一个)元素，则将它与这组元素中的最后一个（第一个）元素交换
• 在剩余的array[i]--array[n-2]（array[i+1]--array[n-1]）集合中，重复上述步骤，直到集合剩余1个元素

//直接选择排序/*时间复杂度：O(N^2)空间复杂度：O(1)稳定性：不稳定*/private static void swap(int[] arr,int i,int j){int temp = arr[i];arr[i]=arr[j];arr[j]=temp;}public static void selectSort(int[] arr){for (int i = 0; i < arr.length; i++) {int minIndex=i;for (int j = i+1; j <arr.length ; j++) {if(arr[j]<arr[minIndex]){minIndex=j;}}swap(arr,minIndex,i);}}

import java.util.Arrays;public class Test {public static void main(String[] args) {//直接选择排序int[] arr2 ={25,14,8,12,20};Sort.selectSort(arr2);System.out.print("直接选择排序：");System.out.println(Arrays.toString(arr2));}
}

 直接选择排序的特性总结：

public static void selectSort(int[] arr){int left=0;int right=arr.length-1;while (left<right){int min=left;int max=left;for (int i = left+1; i <=right ; i++) {if(arr[i]<arr[min]){min=i;}if(arr[i]>arr[max]){max=i;}}swap(arr,min,left);if(max==left){max=min;}swap(arr,max,right);//如果最大值是left下标，上面交换完成后，//最大值跑到最小值的位置，因此需要更新最大值下标left++;right--;}}

上面这两种方法运行出来的结果也是一样的。 

3.2.3堆排序

//堆排序/*时间复杂度：O(N*logN)空间复杂度：O(N)稳定性：不稳定*/private static void createBigHeap(int[] arr){for (int parent = (arr.length-1-1); parent >=0 ; parent--) {siftDown(parent,arr,arr.length);}}private static void siftDown(int parent,int[] arr,int end){int child = 2*parent+1;while(child<end){if(child+1<end && arr[child]<arr[child+1]){child++;}//child下标 就是左右孩子最大值的下标if(arr[child]>arr[parent]){swap(arr,child,parent);parent=child;child=2*parent+1;}else {break;}}}public static void heapSort(int[] arr){createBigHeap(arr);int end = arr.length-1;while(end>=0){swap(arr,0,end);siftDown(0,arr,end);end--;}}

import java.util.Arrays;public class Test {public static void main(String[] args) {//堆排序int[] arr3={65,48,50,25,13};Sort.heapSort(arr3);System.out.print("堆排序：");System.out.println(Arrays.toString(arr3));}
}

堆排序的特性总结：

1.堆排序使用堆来选数，效率高了很多

2.时间复杂度：O(N*log₂N)

3.空间复杂度：O(1)

4.稳定性：不稳定

3.3交换排序

3.3.1基本思想

3.3.2冒泡排序

//冒泡排序/*时间复杂度：O(n^2)空间复杂度：O(N)稳定性：稳定*/public static void bubbleSort(int[] arr) {boolean flg =false;for (int i = 0; i < arr.length - 1; i++) {for (int j = 0; j < arr.length - 1 - i; j++) {if (arr[j] > arr[j + 1]) {swap(arr, j, j + 1);}}//如果第一次排序后是有序的，则结束循环//在优化情况下，时间复杂度：O(N)if(flg==false){break;}}}

import java.util.Arrays;public class Test {public static void main(String[] args) {//冒泡排序int[] arr4={24,35,30,45,10};Sort.bubbleSort(arr4);System.out.print("冒泡排序：");System.out.println(Arrays.toString(arr4));}
}

1. 冒泡排序是一种非常容易理解的排序

2. 时间复杂度： O(N^2)

3. 空间复杂度： O(1)

4. 稳定性： 稳定

3.3.3快速排序

快速排序是 Hoare 于 1962 年提出的一种二叉树结构的交换排序方法，其基本思想为： 任取待排序元素序列中的某元 素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元均小于基准值，右子序列中所有 元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止 。

将区间按照基准值划分为左右两半部分的常见方式有：

1. Hoare版

//快速排序/*Hoare法*/public static void quickSort(int[] arr) {quick(arr, 0, arr.length - 1);}private static void quick(int[] arr, int start, int end) {if (start >= end) {return;}int par = partition(arr, start, end);quick(arr, start, par - 1);quick(arr, par + 1, end);}private static int partition(int[] arr, int left, int right) {int i = left;int temp = arr[left];while (left < right) {while (left < right && arr[right] >= temp) {right--;}while (left < right && arr[left] <= temp) {left++;}swap(arr, left, right);}//left 和 right 相遇swap(arr, left, i);return left;}

import java.util.Arrays;public class Test {public static void main(String[] args) {//快速排序int[] arr5 = {4, 2, 68, 43, 25};Sort.quickSort(arr5);System.out.print("快速排序:");System.out.println(Arrays.toString(arr5));}
}

2.挖坑法

    //快速排序/*挖坑法*/public static void quickSort(int[] arr) {quick(arr, 0, arr.length - 1);}private static void quick(int[] arr, int start, int end) {if (start >= end) {return;}int par = partition1(arr, start, end);quick(arr, start, par - 1);quick(arr, par + 1, end);}private static int partition1(int[] arr, int left, int right) {int temp = arr[left];while (left < right) {while (left < right && arr[right] >= temp) {right--;}arr[left]=arr[right];while (left < right && arr[left] <= temp) {left++;}arr[right]=arr[left];}//left 和 right 相遇arr[left] =temp;return left;}

3.前后指针法

//前后指针法private static int partition2(int[] arr,int left ,int right){int prev =left;int cur= left+1;while (cur<=right){if(arr[cur]<arr[left] && arr[++prev]!=arr[cur]){swap(arr,cur,prev);}cur++;}swap(arr,prev,left);return prev;}

import java.util.Arrays;public class Test {public static void main(String[] args) {//快速排序int[] arr5 = {1,30,25,56,5};Sort.quickSort(arr5);System.out.print("快速排序:");System.out.println(Arrays.toString(arr5));}
}

4.快速排序优化

//快排优化--三数取中法
public static void quickSort(int[] arr) {quick(arr, 0, arr.length - 1);}private static void quick(int[] arr, int start, int end) {if (start >= end) {return;}int index = midThreeNum(arr,start,end);swap(arr,index,end);int par = partition(arr, start, end);quick(arr, start, par - 1);quick(arr, par + 1, end);}private static int midThreeNum(int[] arr,int left,int right){int mid = (left+right)/2;if(arr[mid]<arr[right]){if(arr[mid]<arr[left]){return left;}else if(arr[mid]>arr[right]){return right;}else {return mid;}}else {if(arr[mid]<arr[right]){return right;}else if(arr[mid]>arr[left]){return left;}else {return mid;}}}private static int partition(int[] arr, int left, int right) {int i = left;int temp = arr[left];while (left < right) {while (left < right && arr[right] >= temp) {right--;}while (left < right && arr[left] <= temp) {left++;}swap(arr, left, right);}//left 和 right 相遇swap(arr, left, i);return left;}

import java.util.Arrays;public class Test {public static void main(String[] args) {//快速排序int[] arr5 = {8,6,25,12,10};Sort.quickSort(arr5);System.out.print("快速排序:");System.out.println(Arrays.toString(arr5));}
}

快速排序总结：

1. 快速排序整体的综合性能和使用场景都是比较好的，所以才敢叫快速排序 

2. 时间复杂度：O(N*logN)

3. 空间复杂度：O(logN)

3.4归并排序

3.4.1基本思想

归并排序（ MERGE-SORT ）是建立在归并操作上的一种有效的排序算法 , 该算法是采用分治法（ Divide and Conquer）的一个非常典型的应用。 将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。 若将两个有序表合并成一个有序表，称为二路归并。归并排序核心步骤：

//归并排序/*时间复杂度：O(N*logN)空间复杂度：O(logN)稳定性：稳定*/public static void mergeSort(int[] arr) {mergeSortFun(arr, 0, arr.length - 1);}public static void mergeSortFun(int[] arr, int left, int right) {if (left >= right) {return;}int mid = (left + right) / 2;mergeSortFun(arr, left, mid);mergeSortFun(arr, mid + 1, right);//合并数组merge(arr, left, mid, right);}private static void merge(int[] arr, int left, int mid, int right) {int[] temp = new int[right - left + 1];int k = 0;int s1 = left;int e1 = mid;int s2 = mid + 1;int e2 = right;while (s1 <= e1 && s2 <= e2) {if (arr[s1] <= arr[s2]) {temp[k++] = arr[s1++];} else {temp[k++] = arr[s2++];}}while (s1 <= e1) {temp[k++] = arr[s1++];}while (s2 <= e2) {temp[k++] = arr[s2++];}//temp数组已经有序了，把temp数组的内容拷贝到arr数组里for (int i = 0; i < k; i++) {arr[i + left] = temp[i];}}

import java.util.Arrays;public class Test {public static void main(String[] args) {//归并排序int[] arr7 = {12, 8, 88, 65, 49};Sort.mergeSort(arr7);System.out.print("归并排序：");System.out.println(Arrays.toString(arr7));}
}

归并排序总结：

3.4.2海量数据的排序问题

4.排序算法复杂度及稳定性分析

5.其他非基于比较排序

计数排序

1. 统计相同元素出现次数

2. 根据统计的结果将序列回收到原来的序列中

//计数排序/*时间复杂度：O(MAX(N,范围))空间复杂度：O(范围)稳定性：稳定*/public static void countSort(int[] arr) {//1.遍历数组 求最大值和最小值int minVal = arr[0];int maxVal = arr[0];for (int i = 0; i < arr.length; i++) {if (arr[i] > maxVal) {maxVal = arr[i];}if (arr[i] < minVal) {minVal = arr[i];}}//2.定义一个count数组int n = maxVal - minVal + 1;int[] count = new int[n];//3.遍历arr数组，把值放入计数数组中for (int i = 0; i < arr.length; i++) {int value = arr[i];count[value - minVal]++;}//4.遍历计数组int index = 0;for (int i = 0; i < count.length; i++) {while (count[i] > 0) {arr[index] = i + minVal;index++;count[i]--;}}}

import java.util.Arrays;public class Test {public static void main(String[] args) {//计数排序int[] arr8 = {20,18,26,66,6};Sort.countSort(arr8);System.out.print("计数排序：");System.out.println(Arrays.toString(arr8));}
}

计数排序特性:

1. 快速排序算法是基于 ( ) 的一个排序算法。

A ：分治法    B ：贪心法   C ：递归法    D： 动态规划法

2. 对记录（ 54,38,96,23,15,72,60,45,83 ）进行从小到大的直接插入排序时，当把第 8 个记录 45 插入到有序表时，为找到插入位置需比较( ) 次？（采用从后往前比较）

A: 3     B: 4    C: 5     D: 6

3. 以下排序方式中占用 O(n) 辅助存储空间的是 ( )

A: 简单排序   B: 快速排序   C: 堆排序    D: 归并排序

4. 下列排序算法中稳定且时间复杂度为 O(n^2) 的是 ()

A: 快速排序          B: 冒泡排序         C: 直接选择排序        D: 归并排序

5. 关于排序，下面说法不正确的是 ( )

A: 快排时间复杂度为 O(N*logN) ，空间复杂度为 O(logN)

B: 归并排序是一种稳定的排序 , 堆排序和快排均不稳定

C: 序列基本有序时，快排退化成 " 冒泡排序 " ，直接插入排序最快

D: 归并排序空间复杂度为 O(N), 堆排序空间复杂度的为 O(logN)

6. 设一组初始记录关键字序列为 (65,56,72,99,86,25,34,66) ，则以第一个关键字 65 为基准而得到的一趟快速排序结果是（）

A: 34 ， 56 ， 25 ， 65 ， 86 ， 99 ， 72 ， 66      B: 25 ， 34 ， 56 ， 65 ， 99 ， 86 ， 72 ， 66

C: 34 ， 56 ， 25 ， 65 ， 66 ， 99 ， 86 ， 72      D: 34 ， 56 ， 25 ， 65 ， 99 ， 86 ， 72 ， 66

参考答案：

1.A    2.C    3.D    4.B    5.D    6.A

6.总结

到这里关于七种经典排序算法详解的内容就分享到这，当我们在编写与排序相关的程序，通过画图可以让我们更加清晰明了，能帮助我们更好地理解。