排序算法总结 java实现

发表于   |  

不同的排序算法源于不同的思想。虽然目标是一样的，却有不同的效率，各自的稳定性、是否是原址排序也是有所不同。这里做一个总结，并且附上java实现的代码。具体如下：

  • 基本概念
  • 插入排序
  • 冒泡排序
  • 选择排序
  • 归并排序
  • 堆排序
  • 快速排序

完整代码（包括测试用例）: (https://github.com/FergusChen/AlgoCode)
包路径：main.sort

先说一些概念型的东西，用于描述排序算法：
原址排序：直接在原数组中排序，只需要常数个额外空间。
稳定排序：如果一个排序算法是稳定的，则序列中相同的元素原来有怎样的前后次序，排序后仍然是这样的前后次序。具体来说，对于序列[1,3,5,3,4]， 排序后序列为[1,3,3,4,5]，其中，原来在前面的3仍然在前面，保证两个3的前后次序，这样的排序算法就是稳定的。

插入排序

听到插入排序就想起来左手一副扑克牌，扑克牌的左半部分是已经排好序的，然后逐个抽取右半部分的牌，插入到左半部分的合适位置，直到整副牌都是排好序的。

插入排序就是这样的思想。初始化时左半部分只有1个元素，当然是排好序的啦。然后从右半部分的第1个元素开始，与左半部分已排好序的元素逐个比较，直到找到合适位置（插入后仍使左半部分有序），将该元素插入到此位置就可。

当然，插入的时候就涉及到元素的右移，即把待插入的位置右边的元素(直到待插入的元素)逐个右移，腾出1个元素空间，以存放待插入的元素。特别是当原数组是倒序的，则会有(n-1)!次元素右移，这样的话效率就会比较低。

由上可知，插入排序是原址排序，其最坏运行时间是O(n^2)。并且插入排序是稳定的，因为相等的元素并不右移，所以元素插入后仍然保证前后次序。当待排序数组元素较少，插入排序还是很好的选择。

下面以整型数组为例来实现插入排序，只是演示排序思想。对于自定义对象等的排序，常常可以实现comparable接口，从compareTo方法比较，思想都是一样的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
 * ------插入排序------
 * @param array 待排序数组
 * test: (null), （1个元素的数组），（空数组），(5个无序整数数组)，（6个有序整数数组）
 */
public static void insertSort(int[] array) {
    if (array == null || array.length < 2) {
        return;
    }
    for (int i = 1; i < array.length; i++) {
        int curData = array[i];
        int j = i - 1;
        while(j >= 0 && curData < array[j]){
            array[j + 1] = array[j];
            j--;
        }
        array[j + 1] = curData;
    }
}

冒泡排序

冒泡排序的名字就很形象：就好像从水底开始，相邻两个气泡互相比较，如果下面的比上面的大，就把两个气泡交换，直到最终把整个序列中最大的气泡换到顶部。接下来从下面开始，一步步把次大的气泡换到顶部…… 直到最后，就是一个升序的序列。

冒泡排序也是一种原址排序算法。冒泡排序是稳定的，因为冒泡排序是相邻两个元素交换次序，就算两个元素相等而且判断的条件是if(array[j] >= array[j+1])，那么该相同元素也会交换两次(动手试试就知道了)。但是通常比较时“>”的时候再交换位置。 冒泡排序是时间复杂度是O(n^2)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
 * 冒泡排序
 * @param array 待排序数组
 * test: (null), （1个元素的数组），（空数组），(5个无序整数数组)，（6个有序整数数组）
 */
public static void bubbleSort(int[] array) {
    if (array == null || array.length <= 1) {
        return;
    }
    for (int i = 0; i < array.length; i++) {
        for (int j = 0; j < array.length - i - 1; j++) {
            if (array[j] > array[j + 1]) {
                int temp = array[j];
                array[j] = array[j + 1];
                array[j + 1] = temp;
            }
        }
    }
}

选择排序

选择排序的思想也很简单，就是从序列中选出最小的元素，与序列第1个元素交换位置，然后从剩余元素中选出最小的，与序列第2个元素交换位置……直到序列就剩1个元素了，即是一个排好序的序列。
选择排序也是原址排序，但选择排序是不稳定的。这里可以举个例子说明，如序列[3,6,5,3,1]，在第一趟选择将第1个3和结尾的1交换位置，这样就破坏了两个3的前后次序。选择排序的时间复杂度是O(n^2)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
 * 选择排序
 * @param array 待排序数组
 * test: (null), （1个元素的数组），（空数组），(5个无序整数数组)，（6个无序整数数组）
 * */
public static void selectSort(int[] array){
    if(array == null || array.length <= 1){
        return ;
    }
    for(int i = 0; i < array.length; i++){
        int minIndex = i;
        for(int j = i+1; j < array.length; j++){
            if(array[j] < array[minIndex]){
                minIndex = j;
            }
        }
        int temp = array[i];
        array[i] = array[minIndex];
        array[minIndex] = temp;
    }
}

归并排序

归并排序的思想是“分治、合并”，其关键步骤是把两个有序的序列合并成1个有序序列。那么，有序的序列怎么形成呢？归并排序采用分治的策略，先对序列进行划分（递归），直到划分子序列只有1个元素，1个元素的序列当然是有序的啦，然后就可以将两个只含有1个元素的序列合并成1个含有两个元素的有序序列。总之，就是先划分，再回溯合并，这整个过程就是一个递归的过程。

归并排序的时间复杂度是O(nlgn)，是一种稳定排序。归并排序需要将元素复制到临时数组，临时数组的长度为high - low + 1，因此，归并排序并不是原址排序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
/**
 * 归并排序
 *
 * @param array 待排序数组
 * @param low 待排序数组序列的最低位置
 * @param high 待排序数组序列的最高位置
 * test: (null), （1个元素的数组），（空数组），(5个无序整数数组)，（6个无序整数数组）
 */
public static void mergeSort(int[] array, int low, int high) {
    if (array == null || array.length <= 1) {
        return;
    }
    int mid = (low + high) / 2;
    if (low < high) {
        mergeSort(array, low, mid);
        mergeSort(array, mid + 1, high);
        merge(array, low, mid, high);
    }
}
/**
 * 归并过程
 * @param array 待合并的数组
 * @param low 待合并数组序列的最低位置
 * @param mid 待合并数组序列中划分两个有序序列的位置
 * @param high 待合并数组序列的最高位置
 * 将array中 low到high的元素归并到有序序列，其中，low到mid的序列是有序的，mid+1到high的序列是有序的。
 * */
public static void merge(int[] array, int low, int mid, int high){
    int[] tempArr = new int[high - low + 1];
    int i = low; //i指向已排好序的左序列
    int j = mid + 1;  //j指向已排好序的右序列
    int k = 0; //合并到新数组的指针
        
    //合并过程
    while(i <= mid && j <= high){
        if(array[i] < array[j]){
            tempArr[k++] = array[i++];
        }else{
            tempArr[k++] = array[j++];
        }
    }
    //若左边有序序列有剩余元素，将剩余元素合并到tempArr中
    while(i <= mid){
        tempArr[k++] = array[i++];
    }
    //若右边有序序列有剩余元素，将剩余元素合并到tempArr中
    while (j <= high){
        tempArr[k++] = array[j++];
    }
    //用合并后的有序序列覆盖原数组中的左右两部分序列
    for(k = 0; k < tempArr.length; k++){
        array[k+low] = tempArr[k];
    }
}

堆排序

堆排序涉及到一种比较有意思的数据结构——堆，对于其性质，可以回顾《算法导论》。简单来说，堆就是用数组实现的一颗近似的完全二叉树。最大堆可以保证每一个父结点都大于或等于其子结点。这样最大堆的根节点就是该数组的最大值。

堆排序使用最大堆，需要首先建堆，并且在交换根结点和最后一个结点之后，反复对堆维护。听起来很麻烦，但是因为每次维护堆的时间复杂度是O(lgn)，建堆的时间复杂度是O(nlgn),则堆排序的时间复杂度仍然是O(nlgn)。堆排序是原址排序，但堆排序是不稳定的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
/**
 * 堆排序
 *
 * @param array 待排序的堆
 */
public static void heapSort(int[] array) {
    if (array == null || array.length <= 1) {
        return;
    }
    buildMaxHeap(array);
    for (int i = array.length - 1; i >= 1; i--) {
        exchangeElements(array, 0, i);
        maxHeapify(array, i, 0);
    }
}
/**
 * 维护堆
 * 在这个堆中，只有index位置的元素违背了最大堆的性质，调整该元素的位置，使index位置元素为结点为根的堆仍然是最大堆。
 * 思想：index位置的元素与其左右孩子比较，将三个元素中的最大值与index位置的元素交换，然后递归地向下调整
 *
 * @param array    待维护的堆
 * @param heapSize 堆的元素个数
 * @param index    带调整的元素位置
 */
public static void maxHeapify(int[] array, int heapSize, int index) {
    int left = index * 2 + 1;
    int right = index * 2 + 2;
    int largest = index;
    if (left < heapSize && array[left] > array[index]) {
        largest = left;
    }
    if (right < heapSize && array[right] > array[largest]) {
        largest = right;
    }
    if (largest != index) {
        exchangeElements(array, index, largest);
        maxHeapify(array, heapSize, largest);//递归地向下维护堆
    }
}
/**
 * 新建最大堆
 * @param array 待建堆的数组
 */
public static void buildMaxHeap(int[] array) {
    if (array == null || array.length <= 1) {
        return;
    }
    int mid = (array.length - 1) / 2;
    for (int i = mid; i >= 0; i--) {
        maxHeapify(array, array.length, i);
    }
}

快速排序

快速排序也是使用“分治”的思想，但与归并排序不同的是，快速排序在分治的过程中进行处理次序，具体来说，对于数组A[low ... high]，被划分为两个（可能为空）的子数组A[low ... p-1]和A[p+1 ... high]，使得A[low ... p-1]的元素都小于或等于A[p]，A[p+1 ... high]的元素都大于A[p]。 然后再递归地划分A[low ... p-1]和A[p+1 ... high]。当左右子序列划分都递归到1个元素时，整个序列都是有序的啦。

快速排序的平均时间复杂度为O(nlgn)，最坏时间复杂度是O(n^2)。快速排序的实际性能是几个O(nlgn)中最好的，而且还是原址排序。但是快速排序并不是稳定的排序算法。因为会涉及到元素与主元的交换。举个例子，对于序列[2,3,4,6,6,7,9,5]，以5为主元，当划分之后，元素5需要与第1个6交换位置，这样，就打破了两个6的前后次序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
/**
 * 快速排序
 * @param array 带排序的数组
 * @param low 带排序数组的最低位置
 * @param high 带排序的数组的最高位置
 * test: (null), （1个元素的数组），（空数组），(5个无序整数数组)，（6个无序整数数组）
 */
public static void quickSort(int[] array, int low, int high) {
    if (array == null || array.length <= 1) {
        return;
    }
    if (low < high) {
        int p = randomPartition (array, low, high);
        quickSort(array, low, p - 1);
        quickSort(array, p + 1, high);
    }
}
/**
 * 随机选取数组中的一个数进行划分
 * @param array 带划分的数组序列
 * @param low 带划分数组序列的最低位置
 * @param high 带划分数组序列的最高位置
 * @return int 返回最后划分后，主元的位置    * */
public static int randomPartition(int[] array, int low, int high){
    int i = (int)(low + Math.random()*(high - low + 1)); //产生low到high之间的随机数
    int temp = array[high];
    array[high] = array[i];
    array[i] = temp;
    return partition(array, low, high);
}
/**
 * 划分数组
 * 将array中low 到 high序列划分为两部分，并返回划分元的位置
 * @param array 带划分的数组序列
 * @param low 带划分数组序列的最低位置
 * @param high 带划分数组序列的最高位置
 * @return int 返回最后划分后，主元的位置
 * */
public static int partition(int[] array, int low, int high) {
    int key = array[high]; //主元，即用于划分的元素
    int i = low - 1; //i指向 小于key的序列的尾部
    //j来遍历整个序列，将小于key的元素放到i的左边
    for (int j = low; j < high; j++) {
        if (array[j] <= key) //不仅是小于key，连等于key的元素也交换，以保证划分过程是原址重排
            i++;
            //如果i == j 就无需交换了。
            if(i != j) {
                int temp = array[i];
                array[i] = array[j];
                array[j] = temp;
            }
        }
    }
    //此时，i指向小于key的序列的尾部，则将key与i+1的元素交换，就将整个序列划分为A、B两个部分，其中A：小于或等于key的元素，B：大于key的元素。
    int temp = array[i + 1];
    array[i + 1] = array[high];
    array[high] = temp;
    //返回用于划分的主元的位置。
    return i + 1;
}