快速排序-分治算法_在快速排序中,记录的比较和交换是从两端向中间进行的,关键字较大的记录一次就能交

基本思想

 基于分治策略的排序在快速排序中，记录的比较和交换是从两端向中间进行的，关键字较大（小）的记录一次就能交换到后（前）面单元，总的比较和移动次数较少。

 基本思想：对于输入子数组a[p: r]

1. 分解: 以a[p]为基准元素将a[p: r]划分成三段a[p: q-1], a[q] 和a[q+1:r], 使得a[p: q-1]中任一元素<= a[q], a[q+1:r]中任一元素>= a[q]. q在划分过程中确定.
2. 递归求解: 分别对a[p: q-1]和a[q+1:r]进行递归排序.
3. 合并: 将排好序的a[p: q-1]和a[q+1:r]直接合并, 即得a[p: r].

例子

主要算法

template<class Type>
void QuickSort (Type a[ ], int p, int r)
{
      if (p<r) {
        int q=Partition(a,p,r);
	        QuickSort (a,p,q-1); //对左半段排序
	        QuickSort (a,q+1,r); //对右半段排序
        }
}

template<class Type>
int Partition (Type a[], int p, int r)
{
        int i = p, j = r + 1; 
        Type x=a[p];
        // 将< x的元素交换到左边区域
        // 将> x的元素交换到右边区域
        while (true) {
           while (a[++i] <x);
           while (a[- -j] >x);
           if (i >= j) break; 
           Swap(a[i], a[j]);
           }
       a[p] = a[j];
       a[j] = x;
       return j;
}
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

上述的Partition (Type a[], int p, int r)适用于指定了某个基准元素,然后以该基准元素进行比较

另一种Partition(),其实思想差不多

int Partition (int arr[],int start_,int end_){
      int value=arr[start_];

      while(start_<end_){
            while(start_<end_&&arr[end_]>=value) end_--;
            arr[start_]=arr[end_];
            while(start_<end_&&arr[start_]<=value) start_++;
            arr[end_]=arr[start_];
      }
      arr[end_]=value;
      return end_;
}
1
2
3
4
5
6
7
8
9
10
11
12

复杂度分析

平均时间复杂度