您的位置:首页 - 教程 - C# - 正文
C#实现快速排序

网上很多关于快速排序的教程,嗯,不错,版本也很多,有的试了一下还报错。。呵呵

于是乎低智商的朕花了好几天废了8张草稿纸才弄明白。。

 

快速排序的采用的分治啊挖坑填数啊之类的网上到处都是,具体过程自己百度吧,这里就讲讲我自己写的代码。还有,快排是一种不稳定的排序算法,就是说,当整个数列是无序状态时,效率高,但是,当把一个从大到小的通过排序转成从小到大的,那就呵呵了,随时StackOverflow。。

 

OK,先上代码(排序结果是从小到大)

         static void QuickSort(int[] num, int left, int right)
         {
             if (left >= right)
                 return;
 
             int key = num[left];
             int i = left;
             int j = right;
 
             while (i < j)
             {
                 while (i < j && key < num[j])
                     j--;
                 if (i >= j)
                 {
                     num[i] = key;
                     break;
                 }
                 num[i] = num[j];
 
                 while (i < j && key >= num[i])
                     i++;
                 if (i >= j)
                 {
                     num[i] = key;
                     break;
                 }
                 num[j] = num[i];
             }
             num[i] = key;
 
             QuickSort(num, left, i - 1);
             QuickSort(num, i + 1, right);
         }

参数中的num就不用说了吧,left和right分别代表排序待排序数组的开始和结尾的索引,当然默认排序整个数组的话就:

QuickSort(a, 0, a.Length - 1);

假设待排序数组是a,排序索引是0到最后一项的元素。

 

快排使用分治,选取一个关键值key(代码中的第6行,并且默认使用待排序数组的第一个值),把比它大的和比它小的分别放在两边。

具体就是先从数组右边(j值记录的索引)开始找比key小的数,对应代码的12、13行,至于为什么要i < j,呵呵,待会儿说。

循12行环的意义是,如果当前num[j]比key大,j就自减,直到key>num[j]就找到了比key小或相等的数了呗。

又由于排序的数千变万化,所以有的情况下j一路减下去或记录左边索引的i一路加上去,就有可能i>=j,于是就有了10、12、14、21、23行判断i和j关系的语句了,因为如果i都>=j了,就表示分完了啊。

 于是先假设i一直<j,通过12行的循环找到了比key小或等于的值,就把左右的数交换,不用担心key不见,因为有第6行。。

之后又通过21行的循环找比key大的值,再在28行交换。这样下来10行的大循环完了之后,数组就留了一个“空位”(这个“空位”当然有数,只是它应该被key填充),再在30行用key填充。

之后31、32行递归(别说你不知道啥意思),再对key两边的数进行排序。

排序完成后,i值就对应key的索引,所以递归调用的参数就那样填。。

 

以上纯属个人理解,有错误的地方还请指出!


评论:
  • 2016-06-13 23:03 123