原理:

快速排序也是分治法思想的一种实现,他的思路是使数组中的每个元素与基准值(Pivot,通常是数组的首个值,A[0])比较,数组中比基准值小的放在基准值的左边,形成左部;大的放在右边,形成右部;接下来将左部和右部分别递归地执行上面的过程:选基准值,小的放在左边,大的放在右边。。。直到排序结束。

步骤:

1.找基准值,设Pivot = a[0] 

2.分区(Partition):比基准值小的放左边,大的放右边,基准值(Pivot)放左部与右部的之间。

3.进行左部(a[0] – a[pivot-1])的递归,以及右部(a[pivot+1] – a[n-1])的递归,重复上述步骤。

void QuikSort(int arr[], int length){

    QuikSort(arr,0,length-1);    

}

//low:数组的左边界值,开始为0
//high:数组的右边界值,开始为length-1
void QuikSort(int arr[], int low, int high){
    if(low>=high){    //递归退出条件:只有一个元素时
        return;
    }

    int pivot = arr[low];
    int i=low;
    for(int j=low+1;j<=high;j++){
        if(arr[j]<=pivot){        //a[j] is smaller than pivot
            i++;    //a[i] is bigger than pivot
            if(i!=j){
                Swap(arr[i],arr[j]);
            }
        }
    }
    Swap(arr[low],arr[i]);    //Swap pivot to middle position
    
        //进行分化(partition),递归
    QuikSort(arr,low,i-1);        //a[i] is the pivot now
    QuikSort(arr,i+1,high);
}

void Swap(int &a, int &b){
   int temp = a;
   a = b;
   b = temp;
}

分区(partition)的演示:

 1 #include <iostream>
 2 
 3 using namespace std;
 4 
 5 
 6 void Swap(int &a, int &b){
 7    int temp = a;
 8    a = b;
 9    b = temp;
10 }
11 void QuickSort(int *arr,int low ,int high)
12 {
13     int j=0;
14     int pivot = arr[low];
15     int i = low;
16     if(low>=high)
17     {
18         return;
19     }
20     for(j=low+1;j<=high;j++)
21     {
22         if(arr[j]<=pivot)
23         {
24             i++;
25             if(i!=j)
26             {
27                 Swap(arr[i],arr[j]);
28             }
29         }
30     }
31     Swap(arr[low],arr[i]);
32     QuickSort(arr,low,i-1);
33     QuickSort(arr,i+1,high);
34 }
35 void QuickSortArry(int arr[],int length)
36 {
37     QuickSort(arr,0,length-1);
38 }
39 int p[8]={49,65,97,76,13,27,20,100};
40 int main()
41 {
42     int i=0;
43     cout << "Hello World!" << endl;
44     for(i=0;i<8;i++)
45     cout << p[i]<<" ";
46     cout << endl;
47     QuickSortArry(p,8);
48     for(i=0;i<8;i++)
49     cout << p[i]<<" ";
50     cout << endl;
51     return 0;
52 }

 

版权声明:本文为Rainingday原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://www.cnblogs.com/Rainingday/p/5947486.html