【排序】冒泡排序与快速排序

发表于 | 更新于 | 分类于 > | 次阅读
介绍冒泡排序，冒泡排序的优化；快速排序和快速排序双边扫描的实现

一、冒泡排序（Bubble Sort）

　　冒泡排序是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。 从序列的一端开始往另一端冒泡（你可以从左往右冒泡，也可以从右往左冒泡，看心情），依次比较相邻的两个数的大小（到底是比大还是比小也看你心情）。

　　作为最简单的排序算法之一，冒泡排序给我的感觉就像 Abandon 在单词书里出现的感觉一样，每次都在第一页第一位，所以最熟悉。冒泡排序还有一种优化算法，就是建立一个标志 flag，当在一趟序列遍历中元素没有发生交换，则证明该序列已经有序。

1.算法描述

  1. 比较相邻的元素。如果第一个比第二个大，就交换它们两个；

  2. 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数；

  3. 针对所有的元素重复以上的步骤，除了最后一个；

  4. 重复步骤1~3，直到排序完成。

　　外层循环每比较一次，这一趟中最大的数就沉底，而较小的数则上升一个位置。

2.动图演示

3.代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public static int[] bubbleSort(int[] array) {
    int len = array.length;
    if (len == 0)
        return array;    
    for (int i = 0; i < len - 1; i++){//一共要排序len-1次
        //如果len=5
        //第1次：i=0,需要比较4次，也就是len-1(len-1-i)次
        //第2次：i=1,需要比较3次，也就是len-2(len-1-i)次
        //第3次：i=2,需要比较2次，也就是len-3(len-1-i)次
        //第4次：i=3,需要比较1次，也就是len-4(len-1-i)次，比较完毕
        for (int j = 0; j < len - 1 - i; j++){//选出该趟排序的最大值往后移动
            if (array[j] > array[j+1]) {//相邻元素两两对比
                int temp = array[j+1];	//元素交换	
                array[j+1] = array[j];
                array[j] = temp;
            }
        }
    }
    return array;
}

时间复杂度

最好：O(n)，最坏：O(n2)，平均：O(n2)

4.优化

优化1：优化外层循环

　　若在某一趟排序中未发现气泡位置的交换，则说明待排序的无序区中所有气泡均满足轻者在上，重者在下的原则，因此，冒泡排序过程可在此趟排序后终止。设置一个flag来判断当前数组是否已经有序，如果有序则退出循环，这样可以明显提高冒泡排序的表现。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public static int[] bubbleSortOptimize1(int[] array) {
    int len = array.length;
    if (len == 0)
        return array;
    boolean flag = false;
    for (int i = 0; i < len - 1; i++){
        flag = true;//每次遍历标志位都要先置为true，才能判断后面的元素是否发生了交换
        for (int j = 0; j < len - 1 - i; j++){
            if (array[j] > array[j+1]) {
                flag = false;//只要有发生了交换，flag就置为false
                int temp = array[j+1];	
                array[j+1] = array[j];
                array[j] = temp;
            }
        }
        //如果为true，说明后面的元素已经有序，就直接break
        if(flag){
            break;
        }
    }
    return array;
}

优化2：优化内层循环

　　记住最后一次交换发生位置lastExchange的冒泡排序。

　　在每趟扫描中，记住最后一次交换发生的位置lastExchange（该位置之后的相邻记录均已有序）。下一趟排序开始时，R[1..lastExchange-1]是无序区，R[lastExchange..n]是有序区。这样，一趟排序可能使当前无序区扩充多个记录，因此记住最后一次交换发生的位置lastExchange，从而减少排序的趟数。

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
public static int[] bubbleSortOptimize2(int[] array) {
    int len = array.length;
    if (len == 0)
        return array;
    boolean flag = false;
    int k = len - 1;
    int pos = 0;//pos变量用来标记循环里最后一次交换的位置 
    for (int i = 0; i < len - 1; i++){
        flag = true;
        for (int j = 0; j < k; j++){
            if (array[j] > array[j+1]) {
                flag = false;
                int temp = array[j+1];	
                array[j+1] = array[j];
                array[j] = temp;
                pos = j;//循环里最后一次交换的位置 j赋给pos
            }
        }
        k = pos;
        if(flag){
            break;
        }
    }
    return array;
}

二、快速排序（Quick Sort）

　　快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下，排序 n 个数据要 Ο(nlogn) 次比较。在最坏状况下则需要 Ο(n2) 次比较，但这种状况并不常见。事实上，快速排序通常明显比其他 Ο(nlogn) 算法更快，因为它的内部循环（inner loop）可以在大部分的架构上很有效率地被实现出来。

　　快速排序的核心思想是分治法（Divide and conquer），分而治之，策略是把一个串行（list）分为两个子串行（sub-lists），通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。

　　它的实现方式是每次从序列中选出一个基准值，其他数依次和基准值做比较，比基准值大的放右边，比基准值小的放左边。然后再对左边和右边的两组数分别选出一个基准值，进行同样的比较移动。重复步骤，直到最后都变成单个元素，整个数组就成了有序的序列。

　　快速排序又是一种分而治之思想在排序算法上的典型应用。本质上来看，快速排序应该算是在冒泡排序基础上的递归分治法。

　　快速排序的名字起的是简单粗暴，因为一听到这个名字你就知道它存在的意义，就是快，而且效率高！它是处理大数据最快的排序算法之一了。虽然 Worst Case 的时间复杂度达到了 O(n²)，但是人家就是优秀，在大多数情况下都比平均时间复杂度为 O(nlogn) 的排序算法表现要更好，可是这是为什么呢？我也不知道。好在我的强迫症又犯了，查了 N 多资料终于在《算法艺术与信息学竞赛》上找到了满意的答案：

快速排序的最坏运行情况是 O(n²)，比如说顺序数列的快排。但它的平摊期望时间是 O(nlogn)，且 O(nlogn) 记号中隐含的常数因子很小，比复杂度稳定等于 O(nlogn) 的归并排序要小很多。所以，对绝大多数顺序性较弱的随机数列而言，快速排序总是优于归并排序。　　

1.算法描述

快速排序使用分治法来把一个串（list）分为两个子串（sub-lists）。具体算法描述如下：

  1. 从数列中挑出一个元素，称为 “基准”（pivot）；

  2. 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；

  3. 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。

　　递归的最底部情形，是数列的大小是零或一，也就是永远都已经被排序好了。虽然一直递归下去，但是这个算法总会退出，因为在每次的迭代（iteration）中，它至少会把一个元素摆到它最后的位置去。

2.动图演示

3.代码实现

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
private static int[] quickSort(int[] arr, int startIndex, int endIndex) {
    if (startIndex < endIndex) {
        int partitionIndex = partition(arr, startIndex, endIndex);//切分
        quickSort(arr, startIndex, partitionIndex - 1);
        quickSort(arr, partitionIndex + 1, endIndex);
    }
    return arr;
}
//分区操作
private static int partition(int[] arr, int startIndex, int endIndex) {
    int pivot = arr[startIndex];//设定基准值（pivot）
    int mark = startIndex + 1;//Mark初始化为起始下标
    for (int i = mark; i <= endIndex; i++) {
        if (arr[i] < pivot) {
            swap(arr, i, mark);
            mark++;//小于基准值 则mark+1，并交换位置。
        }
    }
    swap(arr, startIndex, mark - 1);
    return mark - 1;
}

private static void swap(int[] arr, int i, int j) {
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}
1
2
3
4
5
6
7
public static void main(String[] args) {
    int[] arr = {55,22,1,7,20};
    quickSort(arr,0,arr.length-1);
    for (int i = 0; i < arr.length; i++) {
        System.out.print(arr[i]+" ");
    }
}

4.双边扫描

　　另外还有一种双边扫描的做法，看起来比较直观：我们随意抽取一个数作为基准值，然后从数组左右两边进行扫描，先从左往右找到一个大于基准值的元素，将下标指针记录下来，然后转到从右往左扫描，找到一个小于基准值的元素，交换这两个元素的位置，重复步骤，直到左右两个指针相遇，再将基准值与左侧最右边的元素交换。

我们来看一下实现代码，不同之处只有 partition 方法：

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
public static void sort(int[] arr) {
    sort(arr， 0， arr.length - 1);
}

private static void sort(int[] arr， int startIndex， int endIndex) {
    if (endIndex <= startIndex) {
        return;
    }
    //切分
    int pivotIndex = partition(arr， startIndex， endIndex);
    sort(arr， startIndex， pivotIndex-1);
    sort(arr， pivotIndex+1， endIndex);
}


private static int partition(int[] arr， int startIndex， int endIndex) {
    int left = startIndex;
    int right = endIndex;
    int pivot = arr[startIndex];//取第一个元素为基准值

    while (true) {
        //从左往右扫描
        while (arr[left] <= pivot) {
            left++;
            if (left == right) {
                break;
            }
        }
        //从右往左扫描
        while (pivot < arr[right]) {
            right--;
            if (left == right) {
                break;
            }
        }
        //左右指针相遇
        if (left >= right) {
            break;
        }
        //交换左右数据
        int temp = arr[left];
        arr[left] = arr[right];
        arr[right] = temp;
    }

    //将基准值插入序列
    int temp = arr[startIndex];
    arr[startIndex] = arr[right];
    arr[right] = temp;
    return right;
}

　　快速排序的时间复杂度和归并排序一样，O(nlogn)。但这是建立在每次切分都能把数组一刀切两半差不多大的前提下。如果出现极端情况，比如排一个有序的序列，如[ 9，8，7，6，5，4，3，2，1 ]，选取基准值 9 ，那么需要切分 n - 1 次才能完成整个快速排序的过程。这种情况下，时间复杂度就退化成了 O(n2)，当然极端情况出现的概率也是比较低的。

　　所以说，快速排序的时间复杂度是 O(nlogn)，极端情况下会退化成 O(n2)。为了避免极端情况的发生，选取基准值应该做到随机选取，或者是打乱一下数组再选取。

　　另外，快速排序的空间复杂度为 O(1)。

来源：

hustcc/JS-Sorting-Algorithm

1.0 十大经典排序算法

十大经典排序算法（动图演示）

参考：

冒泡排序算法及其两种优化

（完）
谢谢你请我吃糖果！
0%