排序算法

这篇文章中所使用的配图均为网图

这篇文章将会讲解排序算法、对数器、以及如何判定一个算法是否是稳定的

请注意，每个人对算法的思考方式都是不一样的，所以写出来的算法都会存在相对差异，但是算法的思想才是最重要的

排序算法在编程中太常用了，我们很多时候都是调用编程语言中提供的排序算法(多为归并与快排)，但是知道原理就能更好地选择某种排序算法，或者用改写后的排序算法来解决实际应用中的问题

其他知识

关于整型的二进制位

public static void PrintIntegerBinary(int source)
{
    int flag = 0;
    for(int i = 31;i >= 0; i--)
    {
        flag++;
        int bin = 1 << i;
        Console.Write((bin & source) == 0 ? 0 : 1);
        if (flag % 4 == 0)
            Console.Write(" ");
    }
    Console.WriteLine();
}

两数交换

class MySort
{
    // 常见的写法
    public static void Swap(int[] array, int m, int n)
    {
        int temp = array[m];
        array[m] = array[n];
        array[n] = temp;
    }
    // 整型边界值 -2^31 - 2^31 - 1
    // 我的写法 在两数相加越整型边界时失效
    public static void MySwap(int[] array, int m, int n)
    {
        array[m] = array[m] + array[n];
        array[n] = array[m] - array[n];
        array[m] = array[m] - array[n];
    }
    // 一个数 被异或两次同一个数则得到这个数本身
    // 骚气的位运算写法 在两指针指向同一块内存区域时失效
    public static void SwapPlus(int[] array, int m, int n)
    {
        array[m] = array[m] ^ array[n];
        array[n] = array[m] ^ array[n];
        array[m] = array[m] ^ array[n];
    }
}

冒泡排序

时间复杂度O(N ^ 2)

• 从初始位置开始，若下一个数比当前位置的数小，则两数交换，直到数据被完全遍历完毕，此时最大的数据将会出现在数据的最右边
• 重复同一步骤，但结束位置将是此前 数据规模 - 1位置
• 直到已完成排序的数据规模 等于初始的数据规模，此时，整体数据已有序

class MySort
{
    // 冒泡排序
    public static void BubbleSort(int[] array)
    {
        // 如果只有一个数，那么它本身就是有序的
        if (array == null || array.Length < 2) return;
        for (int end = array.Length - 1; end > 0; end--)
        {
            for(int i = 0;i < end; i++)
            {
                if(array[i] > array[i + 1])
                    Swap(array, i, i + 1);
            }
        }
    }
}

选择排序

时间复杂度O(N ^ 2)

• 存在一指针，该指针指向数据的起始位置
• 从未排序区域初始位置开始，若下一个数比当前位置的数小，指针指向下一个数据
• 数据被完全遍历后，此时已经选出未排序区域中最小的数，将其放在未排序区域的第一个位置
• 完成以上步骤后，指针后移一位，重复以上步骤
• 直到排序区域数据规模等于初始数据规模，排序完毕

class MySort
{ 
    // 每次选一个最小值放在最左边 (也可以写成每一次选一个最大值放在最右边原理都是一样的)
    public static void SelectionSort(int[] array)
    {
        if (array == null || array.Length < 2) return;
        // 最小值的索引
        int minIndex;
        for(int i = 0;i < array.Length; i++)
        {
            minIndex = i;
            for(int j = i + 1;j < array.Length; j++)
            {
                if(array[j] < array[minIndex])
                    minIndex = j;
            }
            Swap(array, minIndex, i);
        }
    }
}

对数器

如何验证自己写的算法是否是正确的？手写数据？

• 数据的规模
• 数据本身值的大小
• 测试的问题规模

对数器的作用在于，利用老的算法或效率较差但是结果无异议的算法，来验证新的算法是否是正确的，对数器是非常好用的！

class SortedTest
{
    // 复制一个数组
    public static int[] CopyIntArray(int[] array)
    {
        int[] tmp = new int[array.Length];
        for(int i = 0;i < array.Length; i++)
        {
            tmp[i] = array[i];
        }
        return tmp;
    }
    // 创建随机数据
    public static int[] CreateRandomIntArray(int minVal, int maxVal, int minArrayLength, int maxArrayLength)
    {
        Random random = new Random();
        int[] tmp = new int[random.Next(minArrayLength, maxArrayLength)];
        for(int i = 0;i < tmp.Length; i++)
        {
            tmp[i] = random.Next(minVal, maxVal);
        }
        return tmp;
    }
    // 判断两个数组是否相等
    public static bool ArrayIsEqual(int[] arr1, int[] arr2)
    {
        if (arr1 == null || arr2 == null) return false;
        if (arr1.Length != arr2.Length) return false;
        for(int i = 0;i < arr1.Length; i++)
        {
            if (arr1[i] != arr2[i]) return false;
        }
        return true;
    }
    // 打印数组到终端 用于异常调试
    public static void PrintIntArray(int[] array, string explain)
    {
        Console.Write(explain + ": [ ");
        for (int i = 0;i < array.Length;i++)
        {
            Console.Write(array[i] + " ");
        }
        Console.Write(" ]");
        Console.WriteLine();
    }
}

对数器的使用

public static void Main(string[] args)
{
    // 最小值
    int minVal = -10000;
    // 最大值
    int maxVal = 10000;
    // 数组的最小长度
    int minLength = 0;
    // 数组的最大长度
    int maxLength = 10000;
    // 要测试的次数
    int numberOfTest = 100;
    bool flag = true;

    for (int i = 0; i < numberOfTest; i++)
    {
        // 原数组保留
        int[] sourceArray = SortedTest.CreateRandomIntArray(minVal, maxVal, minLength, maxLength);

        // 复制两组数据，分别测试两种方法
        int[] testArrayOne = SortedTest.CopyIntArray(sourceArray);
        int[] testArrayTwo = SortedTest.CopyIntArray(sourceArray);
        
        // 调用一个排序方法
        MySort.BubbleSort(testArrayOne);
        // 再调用一个排序方法
        MySort.IterationMergeSort(testArrayTwo);
        if (SortedTest.ArrayIsEqual(testArrayOne, testArrayTwo) == false)
        {
            Console.WriteLine("排序出错，出错数据如下:");
            SortedTest.PrintIntArray(sourceArray, "源数据");
            SortedTest.PrintIntArray(testArrayOne, "排序一");
            SortedTest.PrintIntArray(testArrayTwo, "排序二");
            flag = false;
            break;
        }
    }
    if (flag == true) Console.WriteLine("Nice Sort");
}

插入排序

时间复杂度O(N^2)

• 将数据划分为有序区域与未排序区域
• 命中有序区域中的后一个数，也就是未排序区域的第一个数
• 若该数的上一个数比该数小，则将该数与上一个数做交换，直到该条件不满足或已经到数据最左端则停止该过程 (此过程类似插入所以叫做插入排序)
• 当待排序区域数据为空时，所有数据排序完毕

插入排序类似扑克牌整理的过程

class MySort
{
    // 插入排序
    public static void InsertionSort(int[] array)
    {
        if (array == null || array.Length < 2) return;
        // i 是有序区域的变量
        for(int i = 0;i < array.Length - 1;i++)
        {
            // j作为有序区域后的一个变量 不断在有序区域中寻找自己的
            for(int j = i + 1; j > 0 && array[j - 1] > array[j]; j--)
            {
                Swap(array, j - 1, j);
            }
        }
    }
}

分治

分治，字面上的解释是“分而治之”，就是把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。在计算机科学中，分治法就是运用分治思想的一种很重要的算法。分治法是很多高效算法的基础，如排序算法（快速排序，归并排序），傅立叶变换（快速傅立叶变换）等等。

归并排序

时间复杂度O(N * logN)

核心

• 将两组有序的数据合并为一组有序的数据
• 将大规模的数据拆分为个数为1的有序数据 (若数据只有一个时，则该数据必然是有序的)
• 从小规模的有序数据向大规模数据进行合并

递归写法

class MySort
{
    public static void MergeSort(int[] array)
    {
        if (array == null || array.Length < 2) return;
        MergeProcess(array, 0, array.Length - 1);
    }
    public static void MergeProcess(int[] array, int L, int R)
    {
        if (L == R) return;
        int mid = L + ((R - L) >> 1);
        MergeProcess(array, L, mid);
        MergeProcess(array, mid + 1, R);
        Merge(array, L, mid, R);
    }
    // 数组合并
    public static void Merge(int[] array, int L, int M, int R)
    {
        // 将两个有序数组归并到tmp临时数组中
        int[] tmp = new int[R - L + 1];
        // left1是最左边起始位置
        int left1 = L;
        // left2是从中点之后的一个位置作为起始位置
        int left2 = M + 1;
        for(int i = 0;i < tmp.Length; i++)
        {
            if (left1 <= M && left2 <= R)
                tmp[i] = array[left1] < array[left2] ? array[left1++] : array[left2++];
            else if (left1 <= M)
                tmp[i] = array[left1++];
            else if (left2 <= R)
                tmp[i] = array[left2++];
        }
        for(int i = 0;i < tmp.Length; i++)
        {
            array[L + i] = tmp[i];
        }

    }
}

非递归

• 既然已经知道了数据最终会被拆分成规模为1的数据，那么迭代时我们可以直接将1做为起始步长进行衡量要合并的数据
• 步长每次会被 * 2，这是因为有序数据的规模也是这样增长的

class MySort
{
    public static void IterationMergeSort(int[] array)
    {
        if (array == null || array.Length < 2) return;
        int step = 1;
        // 步长一定小于数组总长度
        int L, M, R;
        while(step < array.Length)
        {
            L = 0;
            // 当前指向的那个数也一定小于数组长度
            while (L < array.Length)
            {
                // 数组长度减去L得到差值，差值小于步长说明L - arr.Length之间已经没有或刚好只有step个数了，那么中点位置就等于最末尾的数
                M = array.Length - L >= step ? L + step - 1 : array.Length - 1;
                // 数组长度减去1再减M得到差值，差值大于步长说明M - arr.Length之间已经没有或刚好只有step个数了，那么R位置就等于最末尾的数
                R = array.Length - 1 - M >= step ? M + step : array.Length - 1;
                Merge(array, L, M, R);
                // 如果最右边的数此时已经处于最末尾了，那么说明在该step长度下整个数组已经完全Merge完毕就可以退出了
                if (R == array.Length - 1)
                    break;
                // 如果此时最右边还有数字，那么L往后挪一位来到下一个位置
                L = R + 1;
            }
            // 如果步长已经比数组的一半还要大，那么说明整个数组已经Merge完毕了，此时整组数据已经排序完毕了
            // 因为整型除法是向下取整的，导致信息丢失，所以不能写 >= (大于等于)
            if (step > array.Length / 2)
                break;
            // * 2的操作可以写成向左位移一位的写法
            step <<= 1;
        }
    }
}

快速排序

时间复杂度O(N * logN)

• 选出一组数据中最右边的数，以该数为基准
• 划分两个数据区域分别是小于区域与大于区域
• 指针指向未划分区域中的首个数据，与基数做比较
  • 如果比基数小，则，小于区扩容，并将该数放在小于区域末尾处，然后指针后移
  • 如果比基数大或等于基数，则，大于区扩容，并将该数放在大于区域起始处，指针不变

快排一

初级快排也可以加入随机方法将概率进行散列......

class MySort
{
    public static void QuickSort(int[] array)
    {
        if (array == null || array.Length < 2) return;
        QuickProcess(array, 0, array.Length - 1);
    }
    public static void QuickProcess(int[] array, int L, int R)
    {
        // 当R == L时，数据中只包含一个数据，一个数据必有序
        // 当R < L时，该组数据无效
        if (R <= L) return;
        // 初级快排版本 将数据分为大于区域和小于区域 此时mid位置已经完成排序
        int mid = Partition1(array, L, R);
        // 递归左边的数据
        QuickProcess(array, L, mid - 1);
        // 递归右边的数据
        QuickProcess(array, mid + 1, R);
    }
    // 第一种快排
    public static int Partition1(int[] array, int L, int R)
    {
        // 小于区域初始时处于组数据的最左边 - 1位置
        int less = L - 1;
        // 大于区域处于数据的最右边位置，因为还包含基数
        int more = R;
        // 指针指向组数最左边的起始位置
        int index = L;
        // 如果指针与大于区域相撞，则该过程已被完成
        while(index < more)
        {
            if (array[index] < array[R])
                // 小于区域
                Swap(array, index++, ++less);
            else
                // 大于区域
                Swap(array, index, --more);
        }
        // 最后将基数放在中间位置
        Swap(array, more, R);
        return more;
    }
}

非递归

任何递归版本的代码都可以使用栈进行重写，这是因为递归本身就是方法入栈出栈的过程

二叉树的前序遍历与后序遍历与该思路(代码)都差不多

class MySort
{
    // Task对象用于保存分割完的数组信息
    class Task
    {
        // 保存小于区域信息
        public int L;
        // 保存大于区域信息
        public int R;
        public Task(int L, int R)
        {
            this.L = L;
            this.R = R;
        }
    }
    public static void IterationQuickSort1(int[] array)
    {
        Stack<Task> tasks = new Stack<Task>();
        // 初始时将整个未排序的数据放入栈中
        tasks.Push(new Task(0, array.Length - 1));
        // 当栈中包含数据时，那么数据未排序完成，迭代继续
        while (tasks.Count > 0)
        {
            // 将栈中的数据拿出来进行分割
            Task task = tasks.Pop();
            int val = Partition1(array, task.L, task.R);
            // 存在大于区域
            if (task.R > val)
                // 新的大于区域数据组放入栈中
                tasks.Push(new Task(val + 1, task.R));
            // 存在小于区域
            if (task.L < val)
                // 新的小于区域数据组放入栈中
                tasks.Push(new Task(task.L, val - 1));
        }
    }
}

快排二

荷兰国旗问题

荷兰国旗是由红白蓝3种颜色的条纹拼接而成，如下图所示：

我们把荷兰国旗问题用数组的形式表达一下是这样的：

• 给定一个整数数组，给定一个值K，这个值在原数组中一定存在，要求把数组中小于K的元素放到数组的左边，大于K的元素放到数组的右边，等于K的元素放到数组的中间，最终返回一个整数数组，其中只有两个值，分别是等于K的数组部分的左右两个下标值。

• 例如，给定数组：[2, 3, 1, 9, 7, 6, 1, 4, 5]，给定一个值4，那么经过处理原数组可能得一种情况是：[2, 3, 1, 1, 4, 9, 7, 6, 5]，需要注意的是，小于4的部分不需要有序，大于4的部分也不需要有序，返回等于4部分的左右两个下标，即[4, 4]

荷兰国旗问题引出的第二种快排写法，这与第一种的差别就在于新增了等于区域，若等于区域越大，则算法越快

class MySort
{
    public static void QuickSort(int[] array)
    {
        if (array == null || array.Length < 2) return;
        QuickProcess(array, 0, array.Length - 1);
    }
    public static void QuickProcess(int[] array, int L, int R)
    {
        if (R <= L) return;
        // 荷兰国旗快排版本 mid用于记录等于区域的索引值
        int[] mid = Partition2(array, L, R);
        // L - 等于区域的上一个位置  是小于区域
        QuickProcess(array, L, mid[0] - 1);
        // 等于区域的下一个位置 - R 是大于区域
        QuickProcess(array, mid[1] + 1, R)
    }
        // 第二种快排
    public static int[] Partition2(int[] array, int L, int R)
    {
        int less = L - 1;
        int more = R;
        int index = L;
        while (index < more)
        {
            if (array[index] < array[R])
                Swap(array, index++, ++less);
            else if (array[index] > array[R])
                Swap(array, index, --more);
            else index++;
        }
        Swap(array, more, R);
        return new int[] { less + 1, more };
    }
}

非递归

class MySort
{
    // Task对象用于保存分割完的数组信息
    class Task
    {
        public int L;
        public int R;
        public Task(int L, int R)
        {
            this.L = L;
            this.R = R;
        }
    }

    public static void IterationQuickSort2(int[] array)
    {
        Stack<Task> tasks = new Stack<Task>();
        tasks.Push(new Task(0, array.Length - 1));
        while(tasks.Count > 0)
        {
            Task task = tasks.Pop();
            // 这个和递归版本也是一样的操作，划分出等于区域
            int[] val = Partition2(array, task.L, task.R);
            if (task.R > val[1])
                tasks.Push(new Task(val[1] + 1, task.R));
            if (task.L < val[0])
                tasks.Push(new Task(task.L, val[0] - 1));
        }
    }
}

随机快排

在荷兰国旗的基础上进行概率散列，这样就能使得算法每次的执行时间(次数)相对均衡

• 这是为了处理较坏情况，如[1,2,3,4,5,6,7,8,9]，这样的数据如果每次都选取最右边的数字作为基数，那么整个算法将只有小于区域，整体算法时间复杂度退化为O(N ^ 2)

class MySort
{
    public static void QuickSort(int[] array)
    {
        if (array == null || array.Length < 2) return;
        QuickProcess(array, 0, array.Length - 1);
    }
    public static void QuickProcess(int[] array, int L, int R)
    {
        if (R <= L) return;
        // 随机快排版本
        Swap(array, R, new Random().Next(L, R));
        int[] mid = Partition3(array, L, R);
        QuickProcess(array, L, mid[0] - 1);
        QuickProcess(array, mid[1] + 1, R);

    }
    // 第三种快排
    public static int[] Partition3(int[] array, int L, int R)
    {
        int less = L - 1;
        int more = R;
        int index = L;
        while (index < more)
        {
            if (array[index] < array[R])
                Swap(array, index++, ++less);
            else if (array[index] > array[R])
                Swap(array, index, --more);
            else index++;
        }
        Swap(array, more, R);
        return new int[] { less + 1, more };
    }
}

非递归

随机快排的迭代写法可以同原理转换成非递归 前序/后序 二叉树遍历

    // Task对象用于保存分割完的数组信息
    class Task
    {
        public int L;
        public int R;
        public Task(int L, int R)
        {
            this.L = L;
            this.R = R;
        }
    }
    // 随机快排
    public static void IterationQuickSort3(int[] array)
    {
        Stack<Task> tasks = new Stack<Task>();
        tasks.Push(new Task(0, array.Length - 1));
        while (tasks.Count > 0)
        {
            Task task = tasks.Pop();
            Swap(array, new Random().Next(task.L, task.R), task.R);
            int[] val = Partition3(array, task.L, task.R);
            if (task.R > val[1])
                tasks.Push(new Task(val[1] + 1, task.R));
            if (task.L < val[0])
                tasks.Push(new Task(task.L, val[0] - 1));
        }
    }

稳定性

算法的稳定性在于算法是否做了无用功，如;

假设给定以下数组[ 7,3,9,4,2,6,3] 该数组中包含了重复的数据3，我们给前边的数字编个号，编号为1，后边的数字3编号为2，在排序算法结束后，会得到以下数组:[2,3,3,4,6,7,9]，此时，在排序算法过程中：

• 编号为1的3，始终排在编号为2的3的前边，我们就说这种算法是稳定的
• 相反的若是排序结果或排序过程中出现 顺序被打乱的情况，我们就说这种算法是不稳定的

我们都说快排是不稳定的，但在某种情况下也可以达到稳定状态，相反的，我们说冒泡排序是稳定的，但是你也可以写出不稳定的冒泡排序。

了解更多稳定性知识，可以百度一下，这很容易理解。