快速排序算法最早是由图领奖获得者Tony Hoare设计出来的。希尔排序相当于直接插入排序的升级，同属于插入排序类。堆排序相当于简单选择排序的升级，同属于选择排序类。快速排序是冒泡排序的升级，属于交换类排序，相比较少了总的比较次数和移动交换次数。
快速排序(Quick Sort)的基本思想是：通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，已达到整个序列有序的目的。
主要步凑：
1、先从数列中取出一个数做为基准数。
2、分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。
3、再对左右区间重复第二步，直到各区间只有一个数。
|
#include<iostream>
using namespace std;
//快速排序
int partition(int* arr,int left,int right); //划分数组区间
int quickSort(int* arr,int left,int right);
void swap(int& elem1,int& elem2);
void test();
void printArr(int* arr,int length);
void swap(int& elem1,int& elem2)
{
int tmp = elem1;
elem1 = elem2;
elem2 = tmp;
}
int partition(int* arr,int left,int right)
{
if(NULL==arr||left<0||right<0||left>right)
return -1;
int tmp = arr[left]; //基准元素
#if 0
while(left<right) //循环结束条件就是 left==right
{
while(left<right&&arr[right]>=tmp)
--right;
swap(arr[left],arr[right]);
while(left<right&&arr[left]<=tmp)
++left;
swap(arr[right],arr[left]);
}
arr[left] = tmp;
#endif
//第二种实现
while(left<right)
{
while(left<right&&arr[right]>=tmp)
--right;
if(left<right) //相等表示已经遍历完毕
arr[left++] = arr[right];
while(left<right&&arr[left]<=tmp)
++left;
if(left<right)
arr[right--] = arr[left];
}
arr[left] = tmp;
return left;
}
int quickSort(int* arr,int left,int right)
{
if(NULL==arr||left<0||right<0||left>right)
return -1;
int pos = partition(arr,left,right);
if(-1==pos)
return -1;
quickSort(arr,left,pos-1);
quickSort(arr,pos+1,right);
return 0;
}
|
void printArr(int* arr,int length)
{
if(NULL==arr||length<=0)
return ;
for(int idx=0;idx!=length;++idx)
{
cout<<arr[idx]<<" ";
}
cout<<endl;
}
void test()
{
int arr[] = {6,5,3,1,8,7,2,4};
printArr(arr,8);
quickSort(arr,0,7);
printArr(arr,8);
cout<<endl;
int arr1[] = {1,2,0,-1,5,6,8,3};
printArr(arr1,8);
quickSort(arr1,0,7);
printArr(arr1,8);
cout<<endl;
int arr2[] = {2,2,2,2};
printArr(arr2,4);
quickSort(arr2,0,3);
printArr(arr2,4);
cout<<endl;
int arr3[] = {2,4,1};
printArr(arr3,3);
quickSort(arr3,0,2);
printArr(arr3,3);
cout<<endl;
int arr5[] = {1,2,3,4,5,6,7,8};
printArr(arr5,8);
quickSort(arr5,0,7);
printArr(arr5,8);
cout<<endl;
int* arr6 = NULL;
printArr(arr6,4);
quickSort(arr6,0,3);
printArr(arr6,4);
cout<<endl;
}
int main()
{
test();
system("pause");
}
|