C#排序算法之快速排序

快速排序.gif

1. 快速排序，也叫分治法，是9种经典排序方法中效率最高的。

2. 原理：以升序为例，每轮比较之后，保证基准值左边的数比它小，右边的数比它大。

3. 思路：使用分治法(Divide and conquer)策略来把一个序列(list)分成两个子序列(sub-list)。
   （3.1）从数列中挑出一个元素，称为"基准"(pivot)。
   （3.2）重新排列数列，所有元素比基准值小的摆放在基准左边，所有元素比基准值大的摆放在基准右边。
   ......
   （3.3）递归地(recursive)把小于基准值元素的子数列和大于基准值元素的子数列再次进行排序。
   4.举例：
   （1）要排序的数组是：[15, 22, 35, 9, 16, 33, 15, 23, 68, 1, 33, 25, 14]。

       //相对来说，快速排序数值越大速度越快 。  快速排序是所有排序里面最快的
   class Program
   {
    static void Main(string[] args)
    {
        int[] arr = { 15, 22, 35, 9, 16, 33, 15, 23, 68, 1, 33, 25, 14 }; //待排序数组
        //控制台遍历输出
        Console.WriteLine("排序前的数列：");
        foreach (int item in arr)
            Console.Write(item + " ");
   
   
        QuickSort(arr, 0, arr.Length - 1);  //调用快速排序函数。传值(要排序数组，基准值位置，数组长度)
   
        //控制台遍历输出
        Console.WriteLine();
        Console.WriteLine("排序后的数列：");
        foreach (int item in arr)
            Console.Write(item+" ");
   
        Console.ReadLine();
    }
   
    private static void QuickSort(int[] arr, int begin, int end)
    {
        if (begin >= end) return;   //两个指针重合就返回，结束调用
        int pivotIndex = QuickSort_Once(arr, begin, end);  //会得到一个基准值下标
   
        QuickSort(arr, begin, pivotIndex - 1);  //对基准的左端进行排序  递归
        QuickSort(arr, pivotIndex + 1, end);   //对基准的右端进行排序  递归
    }
   
    private static int QuickSort_Once(int[] arr, int begin, int end)
    {
        int pivot = arr[begin];   //将首元素作为基准
        int i = begin;
        int j = end;
        while (i < j)
        {
            while (arr[j] >= pivot && i < j)  //从右到左，寻找第一个小于基准pivot的元素
            {
                j--; //指针向前移
            }
            arr[i] = arr[j];  //执行到此，j已指向从右端起第一个小于基准pivot的元素，执行替换
   
            
            while (arr[i] <= pivot && i < j) //从左到右，寻找首个大于基准pivot的元素
            {
                i++; //指针向后移
            }
            arr[j] = arr[i];  //执行到此,i已指向从左端起首个大于基准pivot的元素，执行替换
        }
   
        //退出while循环,执行至此，必定是 i= j的情况（最后两个指针会碰头）
        //i(或j)所指向的既是基准位置，定位该趟的基准并将该基准位置返回
        arr[i] = pivot;
        return i;
    }
   

   }
   5.输出结果

   排序前的数列：
   15 22 35 9 16 33 15 23 68 1 33 25 14
   排序后的数列：
   1 9 14 15 15 16 22 23 25 33 33 35 68
   

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

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

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

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