波斯马BOSSMA Information Technology

C#排序算法之快速排序

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

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

看一个标准的实现:

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

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

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

本博客所有文章如无特别注明均为原创。
复制或转载请以超链接形式注明转自波斯马,原文地址《C#排序算法之快速排序

关键字:

建议订阅本站,及时阅读最新文章!
【上一篇】 【下一篇】

发表评论