quick_sort
由于冒泡排序是以相邻元素来比较和交换的，因此，若一个元素离其最终位置较远，则需要进行多次的比较和移动操作。而快速排序则很好的解决了上述问题。
所以，可以说快排是冒泡排序的改进版本。
基本思想：首先选定一个元素作为中间元素，然后将表中所有元素和该元素相比较，将表中比中间元素小的元素调到表的前面，比中间元素大的元素调到表的后
面，再将中间元素放到这两部分之间作为分界点，由此而得到一个划分。然后再对左右两部分分别进行快速排序（即对所得到的两个子表再采用相同的方式来划分和
排序，直到每个子表仅有一个元素或为空表为止，此时便得到一个有序表）。
代码一：
基本思想：p、r分别是待排数组的上下界。首先，用tem存下数组下界元素，腾出空间，待用。i指示的上界的前一个元素空间。如果tem小于a[j]，则不作任何操作。
所以，在tem<=a[j]出现之前，a[j]之前的数组元素中已有若干个大于tem的元素了。当第一次出现tem<=a[j]时，将i递增，此时a[i]中的元素是大于tem的，而此时a[j]是不
大于tem的。对调a[i]、a[j]，就是将小于tem的元素调到数组前面，大于tem的元素调到数组后面。依此往复。遍历到数组最后时，将tem调到i+1的位置即可。（tem就是
所谓的中间元素了）
[cpp] view plain copy print ?
- #include
- using namespace std;
- int partition(int a[],int p,int r)
- {
- int i,j,tem,temp;
- tem=a[r];
- i=p-1;
- for(j=p;j<=r-1;j++)
- {
- if(a[j]<=tem)
- {
- i++;
- temp=a[i];
- a[i]=a[j];
- a[j]=temp;
- }
- }
- temp=a[i+1];
- a[i+1]=a[r];
- a[r]=temp;
- return i+1;
- }
- void quick_sort(int a[],int p,int r)
- {
- int q;
- if(p<r)
- {
- q=partition(a,p,r);
- quick_sort(a,p,q-1);
- quick_sort(a,q+1,r);
- }
- }
- int main()
- {
- int a[100];
- int i,n;
- while(cin>>n,n)
- {
- for(i=0;i<n;i++)
- cin>>a[i];
- int p=0;
- int r=n-1;
- quick_sort(a,p,r);
- for(i=0;i<n;i++)
- cout<<a[i]<<” “;
- cout<<endl<<endl;
- }
- return 0;
}
include
using namespace std;
int partition(int a[],int p,int r)
{int i,j,tem,temp;tem=a[r];i=p-1;for(j=p;j<=r-1;j++){if(a[j]<=tem){i++;temp=a[i];a[i]=a[j];a[j]=temp;}}temp=a[i+1];a[i+1]=a[r];a[r]=temp;return i+1;
}
void quick_sort(int a[],int p,int r){int q;if(p<r){q=partition(a,p,r);quick_sort(a,p,q-1);quick_sort(a,q+1,r);}}int main(){int a[100];int i,n;while(cin>>n,n){for(i=0;i<n;i++)cin>>a[i];int p=0;int r=n-1;quick_sort(a,p,r);for(i=0;i<n;i++)cout<<a[i]<<" ";cout<<endl<<endl;}return 0;}
代码二：
基本思想：把数组最前面的数指定为中间元素，即tem。然后从数组最后开始查找一数小于tem，赋到tem的位置。那么，数组后就空出一位置，此时再从数组
前依次查找一元素大于tem，放到空位置。则数组前又空出一位置。重复上述过程，直到条件不满足。
[cpp] view plain copy print ?
- int partition(int a[],int p,int r)
- {
- int i,j,tem;
- tem=a[p];
- i=p;
- j=r;
- while(i!=j)
- {
- while(i
tem) - j—;
- if(i<j)
- {
- a[i]=a[j];
- i++;
- }
- while(i<j && a[i]<tem)
- i++;
- if(i<j)
- {
- a[j]=a[i];
- j—;
- }
- }
- a[i]=tem;
- return i;
- }
- void quick_sort(int a[],int p,int r)
- {
- int q;
- if(p<r)
- {
- q=partition(a,p,r);
- quick_sort(a,p,q-1);
- quick_sort(a,q+1,r);
- }
}
int partition(int a[],int p,int r)
{int i,j,tem;tem=a[p];i=p;j=r;while(i!=j){while(i<j && a[j]>tem)j--;if(i<j){a[i]=a[j];i++;}while(i<j && a[i]<tem)i++;if(i<j){a[j]=a[i];j--;}}a[i]=tem;return i;
}
void quick_sort(int a[],int p,int r)
{int q;if(p<r){q=partition(a,p,r);quick_sort(a,p,q-1);quick_sort(a,q+1,r);}
}
Attention:
①快排是就地排序，直接在原数组上操作，只需少量的辅助空间。
②平均耗时为O(nlog2n)，并且隐含的常数因子很小，是一般的最佳实用选择。
③每次partition()的过程都可以确定一个数的最终位置。每次partition()中指定的中间元素（tem)，理论上是任意的（代码一指定数组最后的元素，代码二中
指定数组最前面的元素为tem）。
④快速排序是不稳定的。
亦凉
梦里梦外;
怼烎@
还没有评论，来说两句吧...