发布时间 : 2024/5/20 12:27:19 星期一 文章快速排序算法分析解析更新完毕开始阅读c1f2bfb3db38376baf1ffc4ffe4733687f21fc43

快速排序算法

快速排序就是递归调用此过程——在以49为中点分割这个数据序列，分别对前面一部分和后面一部分进行类似的快速排序，从而完成全部数据序列的快速排序，最后把此数据序列变成一个有序的序列，根据这种思想对于上述数组A的快速排序的全过程如图6所示：

初始状态 {49 38 65 97 76 13 27} 进行一次快速排序之后划分为 {27 38 13} 49 {76 97 65} 分别对前后两部分进行快速排序{27 38 13} 经第三步和第四步交换后变成 {13 27 38} 完成排序。{76 97 65} 经第三步和第四步交换后变成 {65 76 97} 完成排序。

运行结果：

27 38 13 49 76 97 65 13 27 38 49 76 97 65 13 27 38 49 65 76 97 第一轮函数调用的详细过程：

{49 38 65 97 76 13 27}

i =0 j=6 Key=49

第一轮循环：i=0 j=6 {27 38 65 97 76 13 27} j=6 {27 38 65 97 76 13 65} i=2 第二轮循环：i=2 j=6 {27 38 13 97 76 13 65} j=5 {27 38 13 97 76 97 65} i=3 第三轮循环：i=3 j=5 {27 38 13 97 76 97 65} j=3 循环结束： i=3 j=3 a[i] = key {27 38 13 49 76 97 65}

C语言版本

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 void sort(int *a, int left, int right) { if(left >= right)/*如果左边索引大于或者等于右边的索引就代表已经整理完成一个组了*/ { return ; } int i = left; int j = right; int key = a[left]; while(i < j) /*控制在当组内寻找一遍*/ { while(i < j && key <= a[j]) /*而寻找结束的条件就是：1，找到一个小于或者大于key的数（大于或小于取决于你想升序还是降序）2，没有符合条件1的，并且i与j的大小没有反转*/ 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 { j--;/*向前寻找*/ } a[i] = a[j]; /*找到一个这样的数后就把它赋给前面的被拿走的i的值（如果第一次循环且key是a[left]，那么就是给key）*/ while(i < j && key >= a[i]) /*这是i在当组内向前寻找，同上，不过注意与key的大小关系停止循环和上面相反，因为排序思想是把数往两边扔，所以左右两边的数大小与key的关系相反*/ { i++; } a[j] = a[i]; } a[i] = key;/*当在当组内找完一遍以后就把中间数key回归*/ sort(a, left, i - 1);/*最后用同样的方式对分出来的左边的小组进行同上的做法*/ sort(a, i + 1, right);/*用同样的方式对分出来的右边的小组进行同上的做法*/ /*当然最后可能会出现很多分左右，直到每一组的i = j 为止*/ }

C++语言

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 #include using namespace std; void Qsort(int a[], int low, int high) { if(low >= high) { return; } int first = low; int last = high; int key = a[first];/*用字表的第一个记录作为枢轴*/ while(first < last) 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 { while(first < last && a[last] >= key) { --last; } a[first] = a[last];/*将比第一个小的移到低端*/ while(first < last && a[first] <= key) { ++first; } a[last] = a[first]; /*将比第一个大的移到高端*/ } a[first] = key;/*枢轴记录到位*/ Qsort(a, low, first-1); Qsort(a, first+1, high); } int main() { int a[] = {57, 68, 59, 52, 72, 28, 96, 33, 24}; Qsort(a, 0, sizeof(a) / sizeof(a[0]) - 1);/*这里原文第三个参数要减1否则内存越界*/ for(int i = 0; i < sizeof(a) / sizeof(a[0]); i++) { cout << a[i] << \ } return 0; }/*参考数据结构p274(清华大学出版社，严蔚敏)*/ Java

1 2 3 4 5 6 7 class Quick { public void sort(int arr[],int low,int high) { int l=low; int h=high; int povit=arr[low]; 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 while(l=povit) h--; if(llow)sort(arr,low,l-1); if(h> T[]quickSort(T[]targetArr,intstart,intend) { inti=start+1,j=end; Tkey=targetArr[start]; SortUtilsUtil=newSortUtil(); if(start>=end)return(targetArr); /*从i++和j--两个方向搜索不满足条件的值并交换 *