首页 > 代码库 > 排序算法之快速排序
排序算法之快速排序
快速排序:冒泡排序的一种改进排序方法
基本思想:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,
然后再按次方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列 。
“快速排序法”使用的是递归原理,下面我结合一个例子来说明“快速排序法”的原理。首先给出一个数组
{53,12,98,63,18,72,80,46, 32,21},先找到第一个数--53,把它作为中间值,也就是说,要把53放
在一个位置,使得它左边的值比它小,右边的值比它大。{21,12,32, 46,18,53,80,72,63,98},这样
一个数组的排序就变成了两个小数组的排序--53左边的数组和53右边的数组,而这两个数组继续用同样的方式
继续下去,一直到顺序完全正确。
结合理论知识整理下几种实现快速排序的算法,可以提供参考的,不足之处,还请多指教!
/*方法一:*/ int sort(int *array, int left, int right) { int i, j, tmp; i=left; j=right; tmp = array[left]; while(i<j) { while(i<j && array[j]>=tmp) { j--; } if(i<j) { array[i] = array[j]; i++; } while(i<j && array[i]<tmp) { i++; } if(i<j) { array[j] = array[i]; j--; } } array[i] = tmp; return i; } void QuickSort1(int *array, int min, int len) { int i; if(min<len) { i=sort(array, min, len); QuickSort1(array, min, i-1); QuickSort1(array, i+1, len); } }
/*方法二:*/ void QuickSort2(int *array, int min, int len) { int i, j, tmp; i = min; j = len; if(i<j) { tmp = array[i]; while(i<j) { while(i<j && array[j]>=tmp) { j--; } if(i<j) { array[i++] = array[j]; } while(i<j && array[i]<tmp) { i++; } if(i<j) { array[j--] = array[i]; } } array[i] = tmp; QuickSort2(array, min, i-1); QuickSort2(array, i+1, len); } }
/*方法三*/ void QuickSort3(int *array, int min, int len) { int i,j,tmp; if(min>len) { return; } i = min; j = len; while(i!=j) { tmp = array[i]; while(i<j && array[j]>tmp) { j--; } if(i<j) { array[i++] = array[j]; } while(i<j && array[i]<tmp) { i++; } if(i<j) { array[j--] = array[i]; } array[i] = tmp; QuickSort3(array, min, i-1); QuickSort3(array, i+1, len); } }提供了测试程序代码,验证下是否正确。
#include<stdio.h> #include<stdlib.h> #include<string.h> void PrintArray(int *array) { int i; for(i=0; i<10; i++) printf("%d ", array[i]); printf("\n"); } int main(int argc, char **argv) { int array[10]={7,2,4,1,3,8,9,6,5,0}; PrintArray(array); //QuickSort1(array, 0, 10); //QuickSort2(array, 0, 10); QuickSort3(array, 0, 10); PrintArray(array); return 0; }
排序算法之快速排序
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。