[数据结构与算法]数据结构-快速排序

时间复杂度：O（nlgn）

不需要额外开辟空间，在原数组的基础上进行排序。

一般用数组中的第一个元素作为标定元素。将标定的元素放大合适的位置中。如下图，左边绿色部分都是小于4的，右侧橙色部分都是大于4的。

?定义两个区间：arr[1+l...j] <4? arr[j+1...i-1]>4,用区间内的数与4比较再别存入其中。从第二个元素开始比较，因此定义i指向第二个元素，j指向l

?初始化时应该保证数组为空。

开始比较，5>4，i++

?再次比较，1<4,j++

交换位置，i++

此时，arr[1+l..j]=arr[1~1] = 1,1纳入了小于4的区间

同理，比较3<4,j++,交换，i++

?6同样如此，

比较2时，2<4，先j++,再交换

再交换位置?

?

?i++

?完成排序

?代码实现：

class QuickSort1
    {
        public static void Sort(int[] arr)
        {
            int n = arr.Length;
            Sort(arr, 0, n - 1);
        }

        private static void Sort(int[] arr,int l,int r)
        {
            //对小规模的数组使用插入排序，避免频繁的递归调用
            if (r - l + 1 <= 15)
            {
                InsertSort.Sort1(arr, l, r);
                return;
            }

            int v = arr[l]; //标定元素v

            int j = l; // arr[l+1...j] < v  arr[j+1...i-1] > v

            //往对应区间填充元素
            for (int i = l+1; i <= r; i++)
            {
                if(arr[i] < v)
                {
                    j++;
                    Swap(arr, i, j);
                }
            }

            //将标定元素放到合适的位置
            Swap(arr, l, j);

            Sort(arr, l, j - 1);  //将左半边arr[l...j-1]排序
            Sort(arr, j + 1, r);  //将右半边arr[j+1...r]排序
        }

        private static void Swap(int[] arr,int i,int j)
        {
            int e = arr[i];
            arr[i] = arr[j];
            arr[j] = e;
        }

快排的局限性：快排有序数组时时间复杂度O(n2)

?改良快排：随机化快速排序

创建一个Random对象：

?//在[l...r]的范围随机一个位置

? int p =l + rd.Next(r - l + 1);??

?将随机的位置与l进行交换使它作为被选择的元素。

//和第一个元素交换作为标定元素，这一步对有序性很强的数组排序有很好的优化。
?Swap(arr, l, p);

?

//随机化的快速排序 O（nlogn）
? ? class QuickSort2
? ? {
? ? ? ? //随机类全局变量，不能写在方法内作为局部变量。
? ? ? ? private static Random rd = new Random();

? ? ? ? public static void Sort(int[] arr)
? ? ? ? {
? ? ? ? ? ? int n = arr.Length;
? ? ? ? ? ? Sort(arr, 0, n - 1);
? ? ? ? }

? ? ? ? private static void Sort(int[] arr, int l, int r)
? ? ? ? {
? ? ? ? ? ? if (r - l + 1 <= 15)
? ? ? ? ? ? {
? ? ? ? ? ? ? ? InsertSort.Sort1(arr, l, r);
? ? ? ? ? ? ? ? return;
? ? ? ? ? ? }

? ? ? ? ? ? //在[l...r]的范围随机一个位置
? ? ? ? ? ? int p =l + rd.Next(r - l + 1);

? ? ? ? ? ? //和第一个元素交换作为标定元素，这一步对有序性很强的数组排序有很好的优化。
? ? ? ? ? ? Swap(arr, l, p);

? ? ? ? ? ? int v = arr[l];

? ? ? ? ? ? int j = l; // arr[l+1...j] < v ?arr[j+1...i-1] > v

? ? ? ? ? ? for (int i = l + 1; i <= r; i++)
? ? ? ? ? ? {
? ? ? ? ? ? ? ? if (arr[i] < v)
? ? ? ? ? ? ? ? {
? ? ? ? ? ? ? ? ? ? j++;
? ? ? ? ? ? ? ? ? ? Swap(arr, i, j);
? ? ? ? ? ? ? ? }
? ? ? ? ? ? }

? ? ? ? ? ? Swap(arr, l, j);
? ? ? ? ? ? Sort(arr, l, j - 1);
? ? ? ? ? ? Sort(arr, j + 1, r);
? ? ? ? }

? ? ? ? private static void Swap(int[] arr, int i, int j)
? ? ? ? {
? ? ? ? ? ? int e = arr[i];
? ? ? ? ? ? arr[i] = arr[j];
? ? ? ? ? ? arr[j] = e;
? ? ? ? }
? ? }

?

?

?

?