心臓から花が咲くように

排序 - 快速排序/归并排序/插入排序

Posted on Edited on Views: Valine: 4.2k 4 mins.

快速排序/归并排序/插入排序

快速排序

快速排序使用分治法（Divide and conquer）策略来把一个串行（list）分为两个子串行（sub-lists）。

  1. 从数列中挑出一个元素，称为 “基准”（pivot）;
  2. 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；partition函数返回pivot的位置。
  3. 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序；（递归改非递归——栈）
1
2
3
4
5
6
public void QuickSort(int[] array,int left,int right){
    if(left >= right) return;//表示已经完成一个组的排序
    int index = Partition(array,left,right);//pivot的位置
    QuickSort(array,left,index - 1);
    QuickSort(array,index + 1,right);
}

Partition的几种写法

1
2
3
4
5
6
7
8
9
10
11
//左右指针partition，分别从左右找到后交换
public int Partition(int[] array,int left,int right){
	int pivot = array[right]; // 确定pivot
	while(left < right){
		while(left < right && array[left] <= pivot){ left++;}
		while(left < right && array[right] >= pivot){ right--;}
		swap(array[left],array[right]);
	}
	swap(array[left],pivot); // 把pivot插到中间
	return left;
}
1
2
3
4
5
6
7
8
9
10
11
12
//挖坑partition，不等左右同时找到，找到一个就覆盖
public int Partition(int[] nums, int left, int right){
    int pivot = nums[left]; // 确定pivot
    while(left < right){
        while(left < right && nums[right] >= pivot){ right--;}
        nums[left] = nums[right];
        while(left < right && nums[left] <= pivot){left++;}
        nums[right] = nums[left];
    }
    nums[left] = pivot;
    return left;
}	
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
//前后指针partition
public int Partition(int[] nums, int left, int right) {
    int pivot = nums[right];
    int i = left - 1;
    for (int j = left; j <= right - 1; j++) {
        if (nums[j] <= pivot) {
            i = i + 1;
            swap(nums[i], nums[j]);
        }
    }
    swap(nums[i + 1], nums[right]);
    return i + 1;
}

public int Partition(int[] array,int left,int right){
    if(left < right){
        int pivot = array[right];
        int cur = left;
        int pre = cur - 1;
        //如果找到小于key的值，并且cur和pre之间有距离时则进行交换。注意两个条件的先后位置不能更换
        while(cur < right){
            while(array[cur] < pivot && pre++ != cur){ swap(array[cur],array[pre]);}
            cur++;
        }
        swap(array[pre++],array[right]);
        return pre;
    }
	return -1;
}

交换元素

1
2
3
4
5
private void swap(int a, int b) {
    int temp = a;
    a = b;
    b = temp;
}

1.基准的选择

(1)固定基准。如果数组元素是随机的，划分过程不产生极端情况，那么程序的运行时间不会有太大的波动。
如果数组元素已经基本有序时，此时的划分就容易产生最坏的情况，即快速排序变成冒泡排序，时间复杂度为O(n^2)。
(2)随机基准。虽然使用随机基准能解决待排数组基本有序的情况，但是由于这种随机性的存在，对其他情况的数组也会有影响(若数组元素是随机的，使用固定基准常常优于随机基准)。
(3)三数取中。选取数组开头，中间和结尾的元素，通过比较，选择中间的值作为快排的基准。其实可以将这个数字扩展到更大(例如5数取中，7数取中等)。这种方式能很好的解决待排数组基本有序的情况，而且选取的基准没有随机性。

2.快速排序分析

快速排序是一种不稳定的排序算法。

  1. 最坏时间复杂度：即元素都分到一个子序列，另一个子序列为空的情况，时间复杂度为O(N2)。
  2. 最好时间复杂度：即序列是均分为两个子序列，时间复杂度是O(NlogN)，与归并排序差不多。
  3. 平均时间复杂度：O(NlogN)。
  4. 空间复杂度：O(logN)

3.快速排序的优化

优化1：序列长度达到一定大小时，使用插入排序

当快排达到一定深度后，划分的区间很小时，再使用快排的效率不高。当待排序列的长度达到一定数值后，可以使用插入排序。由《数据结构与算法分析》(Mark Allen Weiness所著)可知，当待排序列长度为5~20之间，此时使用插入排序能避免一些有害的退化情形。

1
2
3
4
5
6
7
8
9
10
public void QuickSort(int[] array,int left,int right){   
    if (right - left + 1 < 10){
        InsertSort(arr,low,high);
        return;
    }    
    if(left >= right) return;//表示已经完成一个组的排序
	int index = Partition(array,left,right);//pivot的位置
	QuickSort(array,left,index - 1);
	QuickSort(array,index + 1,right);
}

归并排序

采用经典的分治（divide-and-conquer）策略（分治法将问题分(divide)成一些小的问题然后递归求解，而治(conquer)的阶段则将分的阶段得到的各答案”修补”在一起，即分而治之)。

  1. 将数列划分为两部分；
  2. 递归地分别对两个子序列进行归并排序；
  3. 合并两个子序列。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public static void sort(int[] arr, int L, int R) {
    if(L == R) return;
    int mid = L + ((R - L) >> 1);
    sort(arr, L, mid);
    sort(arr, mid + 1, R);
    merge(arr, L, mid, R);
}

public static void merge(int[] arr, int L, int mid, int R) {
    int[] temp = new int[R - L + 1];
    int i = 0;
    int p1 = L;
    int p2 = mid + 1;
    // 比较左右两部分的元素，哪个小，把那个元素填入temp中。先执行语句，执行完后自加
    while(p1 <= mid && p2 <= R) { temp[i++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++];}
    // 上面的循环退出后，把剩余的元素依次填入到temp中
    // 以下两个while只有一个会执行
    while(p1 <= mid) { temp[i++] = arr[p1++];}
    while(p2 <= R) { temp[i++] = arr[p2++];}
    // 把最终的排序的结果复制给原数组
    for(i = 0; i < temp.length; i++) { arr[L + i] = temp[i];}
}

复杂度分析

时间复杂度：O(nlogn)
空间复杂度：O(N)，归并排序需要一个与原数组相同长度的数组做辅助来排序
稳定性：归并排序是稳定的排序算法，temp[i++] = arr[p1] <= arr[p2] ? arr[p1++] : arr[p2++];这行代码可以保证当左右两部分的值相等的时候，先复制左边的值，这样可以保证值相等的时候两个元素的相对位置不变。

插入排序

插入排序与打扑克时整理手上的牌非常类似。摸来的第1张牌无须整理，此后每次从桌上的牌(无序区)中摸最上面的1张并插入左手的牌(有序区)中正确的位置上。为了找到这个正确的位置，须自左向右(或自右向左)将摸来的牌与左手中已有的牌逐一比较。

1
2
3
4
5
6
7
8
9
10
11
12
public void insertionsort(int arr[]){ 
    int n = arr.length; 
    for (int i=1; i<n; i++){ 
        int key = arr[i]; 
        int j = i-1; 
        while (j>=0 && arr[j] > key) { 
            arr[j+1] = arr[j]; 
            j = j-1; 
        } 
        arr[j+1] = key; 
    } 
}

复杂度分析

不稳定排序算法。
最坏情况：$O(n^2)$
最好情况：$O(n) $
平均情况：$O(n^2)$