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 - );

             QuickSort(num, i + , right);

         }

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

QuickSort(a, , a.Length - );

假设待排序数组是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的索引，所以递归调用的参数就那样填。。

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

巴特西

C#实现快速排序

最新文章

热门文章