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(n2),但就平均性能而言,它是基于关键字比较的内部排序算法中速度最快者,快速排序亦因此而得名。它的平均时间复杂度为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();
    
                }
    
            } 
    
    			
  •  

     

    四、下面给出一个简单的排序实例对以上算法进行简单说明

     

    初始数组为--------------> S: 6,10,13,5,8,3,2,11

     

    1、将第一个元素赋值给v----->v = 6;

    2、以v为标准将S进行拆分--->[2,5,3],[6],[8,13,10,11] <----------将得到的数组命名为S1, S2;

    3、同样对子数组S1进行拆分->[ ], [2], [ 5, 3] <--------------------拆分之后,第一个子数组为空。将得到的数组命名为S12;

    4、对子数组S2进行拆分----->[ ], [8], [13, 10, 11]<---------------将得到的数组命名为S22;

    5、此时的数组S为---------->2,5,3,6,8,13,10,11

    6、对子数组S12进行拆分---->[3], [5],[ ];

    7、对自数组S22进行拆分---->[10,11],[13],[]<--------------------将得到的数组命名为S221

    8、此时的数组S为----------->2,3,5,6,8,10,11,13

    9、对子数组S221进行拆分--->[ ], [11], [13]

    10、对后得到的数组为-------->2,3,5,6,8,10,11,13;

    标签: