基础知识

两数交换

基于比较的排序中两数交换是很常见的操作，这里给出了三种写法，不过还是推荐第一种，因为后两种都是有问题的写法，但是仍然有值得学习的地方

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];
    }
}

基础排序算法

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

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

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

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

冒泡排序

bubbleSort

时间复杂度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);
        }
    }
}

插入排序

insertSort

时间复杂度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);
            }
        }
    }
}

分治

分治，字面上的解释是“分而治之”，就是把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解，前人利用这种思想写出了不少优秀的算法。

归并排序

mergeSort

时间复杂度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;
        }
    }
}

快速排序

quickSort

quickSort1

quickSort2

时间复杂度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();
            // 讲末尾位置与L - R位置上的任意数做交换 打散最坏情况出现的可能性
            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));
        }
    }

基于比较的排序