Java—排序

今天我们来介绍一下排序：

        首先，排序是什么：所谓排序就是按照其中的某个或某些关键字的大小，按照升序或者降序的方式把他们排列起来的操作。

        在我们的生活中有很多关于排序的例子：一个班级的学生的成绩排序；在🍑宝上买东西时，这些商品可以按照销量、价格进行排序……

        在介绍排序之前，我们要介绍排序中一个比较重要的概念——稳定性，何为稳定性：稳定性就是在待排序的记录序列中，存在相同的记录，这些相同记录有着一定的顺序，在我们使用某个排序算法对序列进行排序后，这些相同的序列仍然按照之前的顺序存在在序列中，这种排序算法我们称它是稳定的，否则就是不稳定的。

        我们现在介绍的java中的排序主要是基于比较的、原地的、内存的、升序的，接下来就是具体的排序算法的介绍：

1.插入排序

1.1基本思想

1.2画图说明

1.3代码实现

1.4特性

2.希尔排序

2.1基本思想

2.2画图说明

2.3代码实现

2.4特性

3.选择排序

3.1基本思想

3.2画图说明

3.3代码实现

 3.4特性

4.堆排序

4.1基本思想

4.2画图说明

4.3代码实现

4.4特性

5.快速排序

5.1基本思想

5.2画图说明

5.3代码实现

5.4特性

6.冒泡排序

6.1基本思想

6.2画图说明

6.3代码实现

6.4特性

7.归并排序

7.1基本思想

7.2画图说明

7.3代码实现

7.4特性

8.总结

1.插入排序

1.1基本思想

插入排序，顾名思义就是从无序区间中拿出元素，直接插入到有序区间中，知道无序区间的长度为0时，可以得到一个有序序列。

 插入排序一开始将区间分为有序区间和无序区间，有序区间的初始情况应该是只包含一个元素，无序区间的元素个数一直减少，直至没有元素，排序结束。

1.2画图说明

        一个待排序序列，分为[有序序列][无序序列]，在无序序列中拿出第一个元素，与有序序列中的元素进行比较，如果比它大就放在后边，如果比他小就放在前面，如果是和它相同的元素也放在它的后边（保证排序的稳定性）以此类推，就可以得到一个有序序列。

1.3代码实现

1.  
   public static void insertSort(int[] array){
2.  
   //有序数组：[0 , i] 无序数组:[i 1, array.length]
3.  
   for(int i = 0;i < array.length - 1;i ){
4.  
   int x = array[i 1];
5.  
   int j;
6.  
   for(j = i;j >= 0 && array[j] > x;j--){
7.  
   array[j 1] = array[j];
8.  
   }
9.  
   array[j 1] = x;
10.  
    }
11.  
    }

1.4特性

时间复杂度：

最好情况（数组有序）：O(n)

最坏情况（数组逆序）：O(n ^ 2)

平均情况：O(n ^ 2)

空间复杂度：

最好/最坏/平均：O(1)

稳定性：稳定

2.希尔排序

2.1基本思想

希尔排序是插入排序的一个优化，希尔排序又叫缩小增量法，它是先选定一个整数n，把待排序的所有元素分为n组，对组间距离相等的元素进行插排，这时距离相同的元素就变为有序的序列了，重复这个步骤，当所有元素的距离为1时，所有的元素都排好序了。

希尔排序重在选择组数n，一般就是第一次将数组分为2组，进行插排，第二次分为4组，第3次分为8组，以此类推……

2.2画图说明

2.3代码实现

1.  
   public static void shellSort(int[] array){
2.  
   if(array.length == 0){
3.  
   return;
4.  
   }
5.  
   int gap = array.length / 2;
6.  
   while(true){
7.  
   for(int i = gap;i < array.length;i ){
8.  
   int x = array[i];
9.  
   int j;
10.  
    for(j = i - gap; j >= 0 && array[j] > x;j = j - gap){
11.  
    array[j gap] = array[j];
12.  
    }
13.  
    array[j gap] = x;
14.  
    }
15.  
    if(gap == 1){
16.  
    break;
17.  
    }
18.  
    gap = gap / 2;
19.  
    }
20.  
    }

2.4特性

 希尔排序的时间复杂度较复杂，一般都是看作：O(n ^ 1.25)

空间复杂度：O(1)

稳定性：不稳定

3.选择排序

3.1基本思想

选择排序是每次从未排序的区间中拿出最大的一个放到有序区间的起始位置。

区间 = [无序区间][有序区间]

也是使用双重循环，外循环是遍历数组中所有元素（不遍历最后一个，最后一个在排序开始时就自动被看作是有序区间），内循环是将无序区间中的元素和当前最大元素相比，然后进行排序。

3.2画图说明

3.3代码实现

1.  
   public static void selectSort(int[] array){
2.  
   for(int i = 0;i < array.length - 1;i ){
3.  
   int maxIndex = 0;
4.  
   for(int j = 0;j < array.length - i;j ){
5.  
   if(array[j] > array[maxIndex]){
6.  
   maxIndeex = j;
7.  
   }
8.  
   }
9.  
   swap(array,maxIndex,array.length - i - 1);
10.  
    }
11.  
    }
12.  
    public static void swap(int[] array,int i,int j){
13.  
    int tmp = array[i];
14.  
    array[i] = array[j];
15.  
    array[j] = tmp;
16.  
    }

 3.4特性

时间复杂度：

最好/最坏/平均：O(n ^ 2)

空间复杂度：

最好/最坏/平均：O(1)

稳定性：不稳定

4.堆排序

4.1基本思想

堆排序是利用二叉树建堆的一种排序算法，在排升序时，创建大堆，每次都先将堆顶元素和堆中最后一个元素进行交换后，将原来的堆顶元素拿出放入有序区间的起始位置，并且无序区间中减少一个元素。

 在堆排序中，升序要建大堆，降序要建小堆，升序时的区间被划分为[无序区间][有序区间]

在这里有一个需要注意的点，虽然说降序要建小堆(区间分为[有序区间][无序区间])，但是其实这是办不到的，那么要是想排成降序怎么办呢？

在我看来要使用Comparator接口，重新定义大小关系，将本来是小的看作是大的，本来是大的看作小的，然后再按照升序的方法进行排序。

4.2画图说明

4.3代码实现

1.  
   public static void swap(int[] array,int i,int j){
2.  
   int tmp = array[i];
3.  
   array[i] = array[j];
4.  
   array[j] = tmp;
5.  
   }
6.  
   public static void adjustDownBigHeao(int[] array,int size,int index){
7.  
   while(2 * index 1 < size){
8.  
   int maxIdx = 2 * index 1;
9.  
   if(maxIdx 1 < size && array[maxIdx 1] > array[maxIdx]){
10.  
    maxIdx ;
11.  
    }
12.  
    if(array[index] >= array[maxIdx]){
13.  
    return;
14.  
    }
15.  
    swap(array,index,maxIdx);
16.  
    index = maxIdx;
17.  
    }
18.  
    }
19.  
    public static void createBigHeap(int[] array,int size){
20.  
    for(int i = (size - 2) / 2;i >= 0;i--){
21.  
    adjustDownBigHeap(array,size,i);
22.  
    }
23.  
    }
24.  
    public static void heapSort(int[] array){
25.  
    createBigHeap(array,array.length);
26.  
    for(int i = 0;i < array.length - 1;i ){
27.  
    swap(arrat,0,array.length - i - 1);
28.  
    adjustDownBigHeap(array,array.length - i - 1,0);
29.  
    }
30.  
    }

4.4特性

时间复杂度：

最好/最坏/平均：O(n) 或 O(n * log(n))

空间复杂度：

最好/最坏/平均：O(1)

稳定性：不稳定 

5.快速排序

5.1基本思想

快速排序是任取待排序序列中的某元素为基准值，按照大于基准值，小于基准值的规则，左子序列中为小于基准值的元素，右子序列中为大于基准值的元素，然后让左右子序列重复该过程，直到所有元素都排列在相应位置上为止。

快速排序主要有三种方法：①Hoare法、②挖坑法、③前后指针

5.2画图说明

5.3代码实现

1.  
   public static void quickSort(int[] array){
2.  
   quickSortInternal(array,0,array.length - 1);
3.  
   }
4.  
   public static void quickSortInternal(int[] array,int from,int to){
5.  
   if(to - from 1 <= 1){
6.  
   return;
7.  
   }
8.  
   int i = partition3(array,from,to);
9.  
   quickSortInternal(array,from,i - 1);
10.  
    quickSortInternal(array,i 1;to);
11.  
    }
12.  
    public static void swap(int[] array,int i,int j){
13.  
    int tmp = array[i];
14.  
    array[i] = array[j];
15.  
    array[j] = array[i];
16.  
    }
17.  
    //方法1：Hoare法
18.  
    public static int partitionHoare(int[] array int from,int to){
19.  
    int pivot - array[to];
20.  
    int left = from;
21.  
    int right = to;
22.  
    while(left < right){
23.  
    whlie(left < right && array[left] <= pivot){
24.  
    left ;
25.  
    }
26.  
    swap(array,left,right);
27.  
    while(left < right && array[right] >= pivot){
28.  
    right--;
29.  
    }
30.  
    swap(array,left,right);
31.  
    }
32.  
    return right;
33.  
    }
34.  
    //方法2：挖坑法
35.  
    public static int partitionDigHole(int[] array,int from,int to){
36.  
    int pivot = array[to];
37.  
    int left = from;
38.  
    int right = to;
39.  
    while(left < right){
40.  
    while(left < right && array[left] <= pivot){
41.  
    left ;
42.  
    }
43.  
    array[right] = array[left];
44.  
    while(left < right && array[right] >= pivot){
45.  
    right--;
46.  
    }
47.  
    array[left] = array[right];
48.  
    }
49.  
    array[left] = pivot;
50.  
    return left;
51.  
    }
52.  
    //方法3：前后指针法
53.  
    public static int partiton3(int[] array,int from,int to){
54.  
    int pivot = array[to];
55.  
    int b = from;
56.  
    for(int d = from;d < to;d ){
57.  
    if(array[d] < pivot){
58.  
    swap(array,b,d);
59.  
    b ;
60.  
    }
61.  
    }
62.  
    swap(array,b,to);
63.  
    return b;
64.  
    }

5.4特性

时间复杂度：

最好情况：O(n * log(n))

最坏情况：O(n ^ 2)

平均情况：O(n * log(n))

空间复杂度：

最好情况：O(log(n))

最坏情况：O(log(n))

平均情况：O(n)

稳定性：不稳定

6.冒泡排序

6.1基本思想

冒泡排序，就是通过双层循环比较每一个元素，让大的元素放在后边，小的元素放在前面。因为想是气泡在水中冒出，大的先出现，小的后出现，因此成为冒泡排序。

冒泡排序也可以将区间分为有序区间和无序区间，将比较过的已经存在大小顺序的元素放在后边，其他未进行比较的元素放在前面。 

 冒泡排序在实际中运用并不多，但是是一种较为经典的排序算法，所以必须会写！

6.2画图说明

6.3代码实现

1.  
   public static void bubbleSort(int[] array){
2.  
   for(int i = 0;i < array.length - 1;i ){
3.  
   //flag 是用来判断数组中元素是否经过交换
4.  
   boolean flag = true;
5.  
   for(int j = 0;j < array.length - i - 1;j ){
6.  
   if(array[j] > array[j 1]){
7.  
   swap(array,j,j 1);
8.  
   flag = false;
9.  
   }
10.  
    }
11.  
    if(flag){
12.  
    return;
13.  
    }
14.  
    }
15.  
    }
16.  
    public static void swap(int[] array,int i,int j){
17.  
    int tmp = array[i];
18.  
    array[i] = array[j];
19.  
    array[j] = tmp;
20.  
    }

6.4特性

时间复杂度：

最好情况（数组有序）：O(n)

最坏情况（数组逆序）：O(n ^ 2)

平均情况：O(n ^ 2)

空间复杂度：

最好/最坏/平均：O(1)

稳定性：稳定

7.归并排序

7.1基本思想

归并排序是将已经有序的子序列合并，得到完全有序的序列，即先将每个子序列有序，再使子序列段间有序。就是先将一个序列分割成很多个只包含一个元素的序列，然后逐一进行合并排序，最后得到一个有序的序列。

归并排序也可以用在外部排序中。 

7.2画图说明

7.3代码实现

1.  
   public static void mergeSort(int[] array){
2.  
   mergeSortInternal(array,0,array.length);
3.  
   }
4.  
   public static void mergeSortInternal(int[] array,int from,int to){
5.  
   if(to - from <= 1){
6.  
   return;
7.  
   }
8.  
   int mid = from (to - from) / 2;
9.  
   mergeSortInternal(array,from,mid);
10.  
    mergeSortInternal(array,mid,to);
11.  
    merge(array,from,mid,to);
12.  
    }
13.  
    public static void merge(int[] array,int from,int mid,int to){
14.  
    int size = to - from;
15.  
    int[] e = new int[size];
16.  
    int eIdx = 0;
17.  
    int leftIdx = from;
18.  
    int rightIdx = mid;
19.  
    while(leftIdx < mid && right < to){
20.  
    if(array[leftIdx] < array[rightIdx]){
21.  
    e[eIdx] = array[leftIdx];
22.  
    eIdx ;
23.  
    leftIdx ;
24.  
    }else{
25.  
    e[eIdx] = array[right];
26.  
    eIdx ;
27.  
    rightIdx :
28.  
    }
29.  
    }
30.  
    while(left < mid){
31.  
    e[eIdx] = array[leftIdx];
32.  
    eIdx ;
33.  
    leftIdx ;
34.  
    }
35.  
    while(right < to){
36.  
    e[eIdx] = array[rightIdx];
37.  
    eIdx ;
38.  
    rightIdx ;
39.  
    }
40.  
    for(int i = 0;i < size;i ){
41.  
    array[from i] = e[i];
42.  
    }
43.  
    }

7.4特性

时间复杂度：

最好/最坏/平均：O(n * log(n))

空间复杂度：

最好/最坏/平均：O(n)

稳定性：稳定

8.总结

        这篇文章中介绍的排序，使数组的、基于比较的、原地排序的、内存中的、升序的。

        在这7个排序中：按照最好时间复杂度分可分为：①O(n)：插入排序、冒泡排序；②不能达到O(n)：选择排序、希尔排序、堆排序、快速排序、归并排序；按照平均时间复杂度分可分为：①O(n ^ 2)：插入排序、冒泡排序、选择排序；②O(n ^ 1.25):希尔排序；③O(n * log(n))：堆排序、快速排序、归并排序；按照稳定性分可分为：①稳定的：插入排序、冒泡排序、归并排序；②不稳定的：选择排序、快速排序、堆排序；按照算法思想分可分为：①减治思想（将问题的规模逐渐减少，从而得到解决）：插入排序、冒泡排序、选择排序、堆排序；②分治思想（将一个大问题，分成相同的几个小问题解决）：快速排序、归并排序。

这篇好文章是转载于：学新通技术网