C#排序算法之快速排序

发布时间：2010年9月13日 / 分类：DOTNET / 10,613 次浏览 / 评论

前边几篇文章介绍了几种排序的算法，并且针对某些算法做了优化。这篇文章介绍一种比较快速的排序算法：快速排序，可以说是冒泡排序的改进。原理是就是找出一个基准数，然后将小于该数的数字放到左边，大于该数的数字放到右边，这样就完成一轮快速排序，然后左边部分和右边部分分别再进行快速排序，如此递归执行，只有一个数字时就排序完毕了。

看一个标准的实现：

static void QuickSort(int[] intArr)
{
int numberOfLoop = 0;//循环次数
int numberOfSwap = 0;//交换次数
QSort(intArr, 0, intArr.Length - 1, ref numberOfLoop, ref numberOfSwap);
}

static void QSort(int[] intArr, int left, int right, ref int numberOfLoop, ref int numberOfSwap)
{
//如果只有一个元素，就不用排序了
if (left < right) {

//方法一：取第一个数作为基数
                int middle = intArr[left];

                //使用i,j代替left,right
                int i = left;
                int j = right;

                //从后往前找小middle的第一个数，j--
                while (j > i)
                {
                    numberOfLoop++;

                    //如果intArr[j]<middle，则将intArr[j]提前，与i进行交换
                    if (intArr[j] < middle)
                    {
                        numberOfSwap++;

                        int temp = intArr[i];
                        intArr[i] = intArr[j];
                        intArr[j] = temp;

                        //i已经被替换了，再比较也不会大于middle，所以自动加1
                        i++;

                        //从i开始查找大于middle的第一个数，i++
                        while (i < j)
                        {
                            //如果找到，则将intArr[i]与intArr[j]交换，并跳出内循环
                            if (intArr[i] > middle)
                            {
                                numberOfSwap++;

                                temp = intArr[j];
                                //此时intArr[j]已经大于middle
                                intArr[j] = intArr[i];
                                intArr[i] = temp;
                                break;
                            }

                            //如果找到大于middle的数，i++肯定不会执行了，如果找不到，每次都执行
                            i++;
                        }
                    }
                    else
                    {
                        //重复执行从后到前 从前到后的操作
                        j--;
                    }
                }

                if (left != i)
                {
                    QSort(intArr, left, i, ref numberOfLoop, ref numberOfSwap);
                    QSort(intArr, j, right, ref numberOfLoop, ref numberOfSwap);
                }
                else//某些情况下，循环没有找到小于middle的值
                {
                    QSort(intArr, ++i, right, ref numberOfLoop, ref numberOfSwap);
                }
}
}

理解起来稍微有些复杂，就是从后到前找一个比基准数小的值，从前到后找一个比基准数大的值。分别与当前的i值和j值做交换，目的就是将小数放到基准数的前边，大数放到基准数的后边，分成两组，然后分组继续快速排序。

可以对交换部分做一定的改进：

 //方法二：
                //左边索引小于右边，则还未排序完成 　　
                //取中间的元素作为比较基准，小于他的往左边移，大于他的往右边移
                int middle = intArr[(left + right) / 2];
                int i = left - 1;
                int j = right + 1;
                while (true)
                {
                    //从前至后找到大于middle的第一个数，跳出条件是大于等于middle
                    while (intArr[++i] < middle) ;
                    //从后至前找到小于middle的第一个数，跳出条件是小于等于middle
                    while (intArr[--j] > middle) ;

                    if (i >= j)
                        break;

                    //把小数放到前边
                    int temp = intArr[i];
                    intArr[i] = intArr[j];
                    intArr[j] = temp;
                }

                //分组递归快速排序
                QSort(intArr, left, i - 1, ref numberOfLoop, ref numberOfSwap);
                QSort(intArr, j + 1, right, ref numberOfLoop, ref numberOfSwap);

这样就看着简介多了，更容易理解。

经测试，快速排序的效率明显高于前面介绍的接种基本排序方式。