首页 > 代码库 > 快速排序算法分析
快速排序算法分析
关于快速排序算法，由于其有着很好的平均时间复杂度而得到了广泛的应用。
快排的思想：每次从数组中取出一个元素出来，然后将该元素放置到一个合适的位置，使得该元素前面的数都小于或等于该元素，其后面的数都大于或等于该元素。然后在对该元素左右两边的数组进行同样的操作，直到左右两边的元素为空。
比如：有数组：5 3 8 2 6. 取出一个数5， 然后将数组中小于或等于5的数放到5的左边，大于等于5的数放到其右边，然后得到：2 3 5 8 6. 然后在对5左右两边的子数组再进行排序。
根据以上分析，那么通过什么方法来确定取出的元素应当放置的位置呢。在此主要介绍二种方法，
1、严蔚敏版本数据结构中介绍的划分方法
其划分过程如下：
1）将数组的第一个元素取出保存，其值假如为x。并将其第一个位置保存到i。
2）从数组的后面进行遍历，找出第一个小于x的元素，设其下标为j，然后将此元素保存到位置为i的地方。
3）从数组的前面找出第一个大于x的元素，其下标为i,然后将此元素保存到位置为j的地方.
4）若i<j， 则重复步骤2~3, 否则返回i.
其划分代码如下：
int partition2(int arr[], int low, int high){ int tmp; tmp = arr[low]; while(low < high) { while(low < high && arr[high] >= tmp) high--; arr[low] = arr[high]; //swap(arr[low], arr[high]); while(low < high && arr[low] <= tmp) low++; arr[high] = arr[low]; //swap(arr[low], arr[high]); } arr[low] = tmp; return low;}2、算法导论中关于快速排序的划分函数的介绍
其划分过程如下：
1）首先将数组中最后一个元素保存为x。
2）然后从前往后依次比较，若当前元素小于或等于x，则将小于x的元素个数加1，并将当前元素与大于x的第一个元素进行交换。
具体过程见代码。
其划分代码如下：
int partition1(int arr[], int p, int r){ int tmp, hel, i, j; hel = arr[r]; i = p-1; for(j=p; j<r; j++) { if(arr[j] < hel) { i++; swap(arr[i], arr[j]); } } arr[r] = arr[i+1]; arr[i+1] = hel; return i+1;}
代码中用到的交换函数swap如下：
inline void swap(int &a, int &b){ int tmp; tmp = a; a = b; b = tmp;}
快速排序通过每次将一个元素放置到其最终位置，然后将两边的未排序的子数组进行递归。
代码如下：
void qsort(int arr[], int i, int j){ int tmp; if(i < j) { tmp = partition2(arr, i, j); qsort(arr, i, tmp-1); qsort(arr, tmp+1, j); }}
下面写一个测试函数，首先输入数组中元素的个数，然后依次输入每个元素，最后输出排序后的结果。
代码如下：
int main(){ int arr[102], n, i; while(scanf("%d",&n)==1) { for(i=1; i<=n; i++) scanf("%d",&arr[i]); qsort(arr,1, n); for(i=1; i<=n; i++) printf("%d ",arr[i]); printf("\n"); } return 0;}
快速排序算法分析
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。