C#快速排序

时间：2014-7-19类别：编程学习

C#快速排序

C#快速排序

快速排序（Quicksort）是对冒泡排序的一种改进。由C. A. R. Hoare在1962年提出。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

一、该方法的基本思想是

1．先从数列中取出一个数作为基准数。

2．分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。

3．再对左右区间重复第二步，直到各区间只有一个数。

例如

设要排序的数组是A[0]……A[N-1]，首先任意选取一个数据（通常选用第一个数据）作为关键数据，然后将所有比它小的数都放到它前面，所有比它大的数都放到它后面，这个过程称为一趟快速排序。

一趟快速排序的算法是

（1）设置两个变量I、J，排序开始的时候：I=0，J=N-1；

（2）以第一个数组元素作为关键数据，赋值给key，即 key=A[0]；

（3）从J开始向前搜索，即由后开始向前搜索（J=J-1），找到第一个小于key的值a[j]，并与key交换；

（4）从I开始向后搜索，即由前开始向后搜索（I=I+1），找到第一个大于key的a[i]，与key交换；

（5）重复第3、4、5步，直到 I=J； (3,4步是在程序中没找到时候j=j-1，i=i+1。找到并交换的时候i， j指针位置不变。另外当i=j这过程一定正好是i+或j+完成的最后另循环结束)

二、快速排序算法分析

1、快速排序的时间主要耗费在划分操作上，对长度为k的区间进行划分，共需k-1次关键字的比较。

2、最坏情况是每次划分选取的基准都是当前无序区中关键字最小(或最大)的记录，划分的结果是基准左边的子区间为空(或右边的子区间为空)，而划分所得的另一个非空的子区间中记录数目，仅仅比划分前的无序区中记录个数减少一个。时间复杂度为O(n*n)

3、在最好情况下，每次划分所取的基准都是当前无序区的"中值"记录，划分的结果是基准的左、右两个无序子区间的长度大致相等。总的关键字比较次数：O(nlgn)

4、尽管快速排序的最坏时间为O(n²)，但就平均性能而言，它是基于关键字比较的内部排序算法中速度最快者，快速排序亦因此而得名。它的平均时间复杂度为O(nlgn)。

三、C#快速排序代码

C# 代码复制


        public class QuickSort
        ...{

            /**//// <summary> 

            /// 排序 

            /// </summary> 

            /// <param name="numbers">待排序数组</param> 

            /// <param name="left">数组第一个元素索引Index</param> 

            /// <param name="right">数组最后一个元素索引Index</param> 

            private static void Sort(int[] numbers, int left, int right)
            ...{

                //左边索引小于右边，则还未排序完成 

                if (left < right)
                ...{

                    //取中间的元素作为比较基准，小于他的往左边移，大于他的往右边移 

                    int middle = numbers[(left + right) / 2];

                    int i = left - 1;

                    int j = right + 1;

                    while (true)
                    ...{

                        while (numbers[++i] < middle) ;

                        while (numbers[--j] > middle) ;

                        if (i >= j)

                            break;

                        Swap(numbers, i, j);

                    }

                    Sort(numbers, left, i - 1);

                    Sort(numbers, j + 1, right);

                }

            }

            /**//// <summary> 

            /// 交换元素值 

            /// </summary> 

            /// <param name="numbers">数组</param> 

            /// <param name="i">当前左边索引</param> 

            /// <param name="j">当前右边索引</param> 

            private static void Swap(int[] numbers, int i, int j)
            ...{

                int number = numbers[i];

                numbers[i] = numbers[j];

                numbers[j] = number;

            }

            public static void Main()
            ...{

                int[] max = ...{ 6, 5, 2, 9, 7, 4, 0 };

                Sort(max, 0, max.Length - 1);

                StringBuilder temp = new StringBuilder();

                for (int i = 0; i < max.Length; i++)
                ...{

                    temp.Append(max[i].ToString() + ",");

                }

                Console.WriteLine(temp.ToString().Substring(0, temp.Length - 1));

                Console.ReadLine();

            }

        }