Quick Sort 快速排序的原理及实现
原理:
快速排序也是分治法思想的一种实现,他的思路是使数组中的每个元素与基准值(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 }