快速排序

发布时间:2016-12-9 19:47:44 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"快速排序",主要涉及到快速排序方面的内容,对于快速排序感兴趣的同学可以参考一下。

  快排图 设要排序的数组是A[0]……A[N-1],首先任意选取一个数据(通常选用中间的数)作为关键数据,然后将所有比它小的数都放到它前面,所有比它大的数都放到它后面,这个过程称为一趟快速排序。值得注意的是,快速排序不是一种稳定的排序算法,也就是说,多个相同的值的相对位置也许会在算法结束时产生变动。 一趟快速排序的算法是: 1)设置两个变量i、j,排序开始的时候:i=0,j=N-1; 2)以第一个数组元素作为关键数据,赋值给key,即key=A[0]; 3)从j开始向前搜索,即由后开始向前搜索(j--),找到第一个小于key的值A[j],将值为key的项与A[j]交换; 4)从i开始向后搜索,即由前开始向后搜索(i++),找到第一个大于key的A[i],将值为key的项与A[i]交换; 5)重复第3步 6)重复第3、4、5步,直到i=j; (3,4步中,没找到符合条件的值,即3中A[j]不小于key,4中A[j]不大于key的时候改变j、i的值,使得j=j-1,i=i+1,直至找到为止。找到符合条件的值,进行交换的时候i, j指针位置不变。另外,i==j这一过程一定正好是i+或j-完成的时候,此时令循环结束)。 排序演示 假设用户输入了如下数组: 下标 0 1 2 3 4 5 数据 6 5 7 3 8 9 现在,创建变量i=0(指向第一个数据), j=5(指向最后一个数据), k=6(赋值为第一个数据的值)。 现在我们取走了下标0的数据,于是,我们现在需要找到一个数字来替换他。由于我们要把所有比6小的数移动到左面,所以我们可以开始寻找比6小的数啦。别急,我们要按顺序找哦。现在不断递减j的值,我们发现下标3的数据比6小,于是把3移到下标0(实际是i指向的位置。代码中要用i,因为后面还会循环这个步骤,不用i的话第二次循环就会出问题。),数组和变量变成了以下状态: 下标 0 1 2 3 4 5 数据 3 5 7 3 8 9 i=0 j=3 k=6 由于变量k已经储存了下标0的数据,所以我们可以放心的把下标0覆盖了。如此一来,下标3虽然有数据,但是相当于没有了,因为数据已经复制到别的地方了。于是我们再找一个数据来替换他。这次要变成找比k大的了,而且要从前往后找了。递加变量i,发现下标2是第一个比k大的,于是用下标2的数据7替换j指向的下标3的数据,数据状态变成下表: 下标 0 1 2 3 4 5 数据 3 5 7 7 8 9 i=2 j=3 k=6 现在重复上面的步骤,递减变量j。这时,我们发现i和j“碰头”了:他们都指向了下标2。于是,循环结束,把k填回下标2里,即得到结果。 如果i和j没有碰头的话,就递加i找大的,还没有,就再递减j找小的,如此反复,不断循环。注意判断和寻找是同时进行的。 注意:这里的数据给的不太好,实际上这样排序以后不会得到最终结果,只会把比k大和比k小的数分到k的两边。(你可以想象一下i和j是两个机器人,数据就是大小不一的石头,先取走i前面的石头留出回旋的空间,然后他们轮流分别挑选比k大和比k小的石头扔给对面,最后在他们中间把取走的那块石头放回去,于是比这块石头大的全扔给了j那一边,小的全扔给了i那一边。只是这次运气好,扔完一次刚好排整齐。)为了得到最后结果,需要再次对下标2两边的数组分别执行此步骤,然后再分解数组,直到数组不能再分解为止(只有一个数据),才能得到正确结果。 示例代码 C++语言 ? 1 2 3 4 5 6 7 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 #include <iostream> #include <ctime>   using namespace std; int partion(int a[],int p,int r){     //rand     srand((unsigned)time( NULL));     int e=rand()%(r-p+1)+p;     int tem;     tem=a[e];     a[e]=a[r];     a[r]=tem;     int x=a[r], i=p-1;     for (int j=p;j<r;j++){          if (a[j]<=x){             tem=a[i+1];             a[i+1]=a[j];             a[j]=tem;             i++;         }     }     tem=a[r];     a[r]=a[i+1];     a[i+1]=tem;     return i+1; }    void QuickSort(int a[],int p,int r){     if (p<r){         int q=partion(a,p,r);         QuickSort(a,p,q-1);         QuickSort(a,q+1,r);     } }    int main(){     int array[]={0,-2,11,-4,13,-5,14,-43};     QuickSort(array,0,7);     for(int i=0;i<=7;i++)         cout<<array[i]<<" ";     cout<<endl;     return 0;  } C++递归 void quickSort(int *a,size_t left,size_t right) {    /*    size_t p = (left + right)/2;     可能会溢出    */ size_t p = (left & right) + ((left ^ right) >> 1 ); int key = a[p]; for(size_t i = left,j = right; i < j;) {        while(key >= a[i] && p >= i) i++; if(i < p) { a[p] = a[i]; p = i; } while(j >= p && a[j] >= key)) j--; if(p < j) { a[p] = a[j]; p = j; } } a[p] = key; if(p - left > 1) quickSort(a,left,p-1); if(right - p > 1) quickSort(a,p + 1, right);} Java public static void quickSort(int a[], int start, int end) {        int i,j; i = start; j = end; if((a==null)||(a.length==0)) return; while(i<j) { while(i<j&&a[i]<=a[j])     //以数组start下标的数据为key,右侧扫描 j--; if(i<j){                   //右侧扫描,找出第一个比key小的,交换位置 int temp = a[i]; a[i] = a[j]; a[j] = temp; } while(i<j&&a[i]<a[j])    //左侧扫描(此时a[j]中存储着key值) i++; if(i<j){                 //找出第一个比key大的,交换位置 int temp = a[i]; a[i] = a[j]; a[j] = temp; } } if(i-start>1) {                //递归调用,把key前面的完成排序 quickSort(a,0,i-1); } if(end-j>1) { quickSort(a,j+1,end);    //递归调用,把key后面的完成排序 } } C# using System; using System.Collections.Generic; using System.Linq; using System.Text; namespace test { class Program { static void Main(string[] args) { int[] array = { 49, 38, 65, 97, 76, 13, 27 }; sort(array, 0, array.Length - 1); Console.ReadLine(); }        /*        * 一次排序单元,完成此方法,key左边都比key小,key右边都比key大。 * @param array 排序数组 * @param low 排序起始位置 * @param high 排序结束位置 * @return 单元排序后的数组        */ private static int sortUnit(int[] array, int low, int high) { int key = array[low]; while (low < high) {                //从后向前搜索比key小的值 while (array[high] >= key && high > low) --high;                         //比key小的放左边 array[low] = array[high];           //从前向后搜索比key大的值,比key大的放右边 while (array[low] <= key && high > low) ++low;                              //比key大的放右边 array[high] = array[low]; }                                            //左边都比key小,右边都比key大。            //将key放在游标当前位置。            //此时low等于high array[low] = key; Console.WriteLine(array.ToString()); return high; }        /*        * 快速排序        * @param arry        * @return        */ public static void sort(int[] array, int low, int high) { if (low >= high) return;                            //完成一次单元排序 int index = sortUnit(array, low, high);             //对左边单元进行排序 sort(array, low, index - 1);                        //对右边单元进行排序 sort(array, index + 1, high);        } } }

上一篇:12个有趣的C语言面试题
下一篇:主键自增插值失败后修改主键自增ID值

相关文章

关键词: 快速排序

相关评论