0620学习

agile Posted on Jun 20 2023

面试排序算法 leetcode学习

<table><thead><tr><th>排序算法</th><th>平均时间复杂度</th><th>最好情况</th><th>最坏情况</th><th>空间复杂度</th><th>排序方式</th><th>稳定性</th></tr></thead><tbody><tr><td>冒泡排序</td><td>O(n<sup>2</sup>)</td><td>O(n)</td><td>O(n<sup>2</sup>)</td><td>O(1)</td><td>In-place</td><td>稳定</td></tr><tr><td>选择排序</td><td>O(n<sup>2</sup>)</td><td>O(n<sup>2</sup>)</td><td>O(n<sup>2</sup>)</td><td>O(1)</td><td>In-place</td><td>不稳定</td></tr><tr><td>插入排序</td><td>O(n<sup>2</sup>)</td><td>O(n)</td><td>O(n<sup>2</sup>)</td><td>O(1)</td><td>In-place</td><td>稳定</td></tr><tr><td>希尔排序</td><td>O(n log n)</td><td>O(n log<sup>2</sup> n)</td><td>O(n log<sup>2</sup> n)</td><td>O(1)</td><td>In-place</td><td>不稳定</td></tr><tr><td>归并排序</td><td>O(n log n)</td><td>O(n log n)</td><td>O(n log n)</td><td>O(n)</td><td>Out-place</td><td>稳定</td></tr><tr><td>快速排序</td><td>O(n log n)</td><td>O(n log n)</td><td>O(n<sup>2</sup>)</td><td>O(log n)</td><td>In-place</td><td>不稳定</td></tr><tr><td>堆排序</td><td>O(n log n)</td><td>O(n log n)</td><td>O(n log n)</td><td>O(1)</td><td>In-place</td><td>不稳定</td></tr><tr><td>计数排序</td><td>O(n + k)</td><td>O(n + k)</td><td>O(n + k)</td><td>O(k)</td><td>Out-place</td><td>稳定</td></tr><tr><td>桶排序</td><td>O(n + k)</td><td>O(n + k)</td><td>O(n<sup>2</sup>)</td><td>O(n + k)</td><td>Out-place</td><td>稳定</td></tr><tr><td>基数排序</td><td>O(n x k)</td><td>O(n x k)</td><td>O(n x k)</td><td>O(n + k)</td><td>Out-place</td><td>稳定</td></tr></tbody></table>

相关术语解释：

*   稳定：如果 a 原本在 b 前面，而 a=b，排序之后，a 仍然在 b 的前面
*   不稳定：不满足稳定定义
*   内排序（In-place）：所有排序操作都在内存中完成
*   外排序（Out-place）：由于数据太大，因此把数据放在磁盘中，而排序通过磁盘和内存的数据传输才能进行。
*   时间复杂度：一个算法执行所耗费的时间
*   空间复杂度：运行完一个程序所需内存的大小
*   n：数据规模
*   k：「桶」的个数
*   In-place：不占用额外内存
*   Out-place：占用额外内存

---

常见算法的稳定性（要记住）

###不稳定排序算法

`堆排序、快速排序、希尔排序、选择排序`

###稳定排序算法

`基数排序、冒泡排序、插入排序、桶排序、归并排序 计数排序`

---

-   冒泡排序
```C#
// 首先，对n个元素执行“冒泡”，将数组的最大元素交换至正确位置，
// 接下来，对剩余 n-1个元素执行“冒泡”，将第二大元素交换至正确位置。
// 以此类推，经过n-1轮“冒泡”后，前 n-1大的元素都被交换至正确位置。
// 仅剩的一个元素必定是最小元素，无需排序，因此数组排序完成。
public void BubbleSort(int[] array)
{
    var length = array.Length;
    var flag = false;
    for (var i = 0; i < length; i++)
    {
        for (var j = 1; j < length - i; j++)
        {
            var a = array[j - 1];
            var b = array[j];
            if (a > b)
            {
                (array[j - 1], array[j]) = (b, a);
                flag = true;
            }
        }

if (!flag)
        {
            break;
        }
    }
}
```

---

- 选择排序
```C#
// 1.初始状态下，所有元素未排序，即未排序（索引）区间为 [0,n-1]。
// 2.选取区间[0,n-1]中的最小元素，将其与索引0处元素交换。完成后，数组前1个元素已排序。
// 3.选取区间[1,n-1]中的最小元素，将其与索引1处元素交换。完成后，数组前2个元素已排序。
// 4.以此类推。经过n-1轮选择与交换后，数组前n-1个元素已排序。
// 5.仅剩的一个元素必定是最大元素，无需排序，因此数组排序完成。
public void SelectionSort(int[] array)
{
    var length = array.Length;
    for (var i = 0; i < length; i++)
    {
        for (var j = i + 1; j < length; j++)
        {
            if (array[j] < array[i])
            {
                (array[i], array[j]) = (array[j], array[i]);
            }
        }
    }
}
```

---

-   插入排序
```C#
// 1.初始状态下，数组的第 1 个元素已完成排序。
// 2.选取数组的第 2 个元素作为 base ，将其插入到正确位置后，数组的前 2 个元素已排序。
// 3.选取第 3 个元素作为 base ，将其插入到正确位置后，数组的前 3 个元素已排序。
// 4.以此类推，在最后一轮中，选取最后一个元素作为 base ，将其插入到正确位置后，所有元素均已排序。
public void InsertionSort(int[] array)
{
    var length = array.Length;
    for (var i = 1; i < length; i++)
    {
        var baseValue = array[i];
        var j = i - 1;
        for (; j >= 0; j--)
        {
            if (array[j] > baseValue)
            {
                array[j + 1] = array[j];
            }
            else
            {
                break;
            }
        }

array[j + 1] = baseValue;
    }
}
```

---

-   二分插入排序

```C#
private int __BinarySearch(int[] array, int right, int key)
{
    var left = 0;
    while (left <= right)
    {
        var mid = (left + right) / 2;
        if (array[mid] == key)
        {
            return mid + 1;
        }

if (array[mid] > key)
        {
            right = mid - 1;
        }

if (array[mid] < key)
        {
            left = mid + 1;
        }
    }

// 结束循环时，left必定等于right+1
// 最后一次查找如果是查找左半边，则key比arr[mid]小，key应该插入到mid的位置，而mid等于现在的right+1等于left
// 最后一次查找如果是查找右半边，则key比arr[mid]大，key应该插入到mid+1的位置，而mid+1等于现在的left
// 所以只需返回left
    return left;
}

// 二分插入排序
public void BinaryInsertSort(int[] array)
{
    for (var i = 1; i < array.Length; i++)
    {
        var key = array[i];
        var index = __BinarySearch(array, i - 1, key);
    //    if (index < i)
        {
            var j = i - 1;
            for (; j >= index; j--)
            {
                //if (array[j] > key)
                {
                    array[j + 1] = array[j];
                }
                //else
                {
                  //  break;
                }
            }

array[j + 1] = key;
        }
    }
}
```

---

-   希尔排序
希尔排序(Shell Sort)是插入排序的一种，它是针对直接插入排序算法的改进。因为当一个数组的大部分元素是从大到小排列，用插入排序来从小到大排序的话，效率会被降低（需要做很多次swap），这种情况用希尔排序就会提升排序效率。它通过比较相距一定间隔的元素来进行，各趟比较所用的距离随着算法的进行而减小，直到只比较相邻元素的最后一趟排序为止。

---
希尔排序的效率取决于增量值gap的选取，时间复杂度并不是一个定值。

开始时，gap取值较大，子序列中的元素较少，排序速度快，克服了直接插入排序的缺点；其次，gap值逐渐变小后，虽然子序列的元素逐渐变多，但大多元素已基本有序，所以继承了直接插入排序的优点，能以近线性的速度排好序。

---

```C++
template<typename T>
void Sorts::ShellSort(T *array, size_t len, std::function<int(const T &, const T &)> compare) {
    for (int gap = (int) len >> 1; gap > 0; gap = gap >> 1) {
        //每一组有多少个成员
        int item_nums = (int) len / gap;
        //遍历每一组
        for (int gap_index = 0; gap_index < gap; ++gap_index) {
            //开始排序的组员index
            int start = gap_index * item_nums + 1;
            //结束组员的index,不包括这个end
            int end = (gap_index + 1) * (item_nums) + 1;
            //上一组最后index
            int last_end = start - 1;
            end = end > len ? (int) len : end;
            for (int i = start; i < end; ++i) {
                int j = i - 1;
                auto t = array[i];
                for (; j >= last_end; j--) {
                    if (compare(array[j], t) > 0) {
                        array[j + 1] = array[j];
                    } else {
                        break;
                    }
                }
                array[j + 1] = t;
            }
        }
    }
}
```

---

-   快速排序
```C#
// 1.首先，对原数组执行一次「哨兵划分」，得到未排序的左子数组和右子数组；
// 2.然后，对左子数组和右子数组分别递归执行「哨兵划分」；
// 3.持续递归，直至子数组长度为 1 时终止，从而完成整个数组的排序；
public void QuickSort(int[] array)
{
    var length = array.Length;
    if (length <= 1)
    {
        return;
    }

// __QuickSort(array, 0, length - 1);
    __QuickSortTailRecursive(array, 0, length - 1);
}

private void __QuickSort(int[] array, int left, int right)
{
    if (left >= right)
    {
        return;
    }

// 哨兵划分
    var mid = __Partition(array, left, right);
    // 递归左子数组、右子数组
    __QuickSort(array, left, mid - 1);
    __QuickSort(array, mid + 1, right);
}

//尾递归
// 为了防止栈帧空间的累积，我们可以在每轮哨兵排序完成后，
// 比较两个子数组的长度，仅对较短的子数组进行递归。由于较短子数组的长度不会超过
// ，因此这种方法能确保递归深度不超过 
// ，从而将最差空间复杂度优化至 。
private void __QuickSortTailRecursive(int[] array, int left, int right)
{
    while (left < right)
    {
        var mid = __Partition(array, left, right);
        // 对两个子数组中较短的那个执行快排
        if (mid - left < right - mid)
        {
            // 递归排序左子数组
            __QuickSortTailRecursive(array, left, mid - 1);
            left = mid + 1; // 剩余未排序区间为 [mid + 1, right]
        }
        else
        {
            // 递归排序右子数组
            __QuickSortTailRecursive(array, mid + 1, right);
            right = mid - 1; // 剩余未排序区间为 [left, mid - 1]
        }
    }
}

// 快速排序在某些输入下的时间效率可能降低。举一个极端例子，假设输入数组是完全倒序的，
// 由于我们选择最左端元素作为基准数，那么在哨兵划分完成后，基准数被交换至数组最右端，
// 导致左子数组长度为 、右子数组长度为。如此递归下去，每轮哨兵划分后的右子数组长度都为 ，
// 分治策略失效，快速排序退化为「冒泡排序」.
// 我们可以在数组中选取三个候选元素（通常为数组的首、尾、中点元素），并将这三个候选元素的中位数作为基准数

private int __MiddleData(int[] array, int left, int midIndex, int right)
{
    if (array[left] < array[midIndex] ^ array[left] < array[right])
    {
        return left;
    }

if (array[right] < array[left] ^ array[right] < array[midIndex])
    {
        return right;
    }

return midIndex;
}

private int __Partition(int[] array, int left, int right)
{
    var midIndex = __MiddleData(array, left, (left + right) / 2, right);
    __Swap(array, midIndex, left);
    midIndex = left;
    var midData = array[midIndex];
    while (left < right)
    {
        while (left < right && array[right] >= midData)
        {
            right--;
        }

while (left < right && array[left] <= midData)
        {
            left++;
        }

__Swap(array, left, right);
    }

__Swap(array, midIndex, left);
    return left;
}

private void __Swap(int[] array, int i, int j)
{
    (array[i], array[j]) = (array[j], array[i]);
}
```

---

-   归并排序

```C#
// 1.计算数组中点 mid ，递归划分左子数组（区间 [left, mid] ）和右子数组（区间 [mid + 1, right] ）；
// 2.递归执行步骤 1. ，直至子数组区间长度为 1 时，终止递归划分；
// “合并阶段”从底至顶地将左子数组和右子数组合并为一个有序数组。需要注意的是，从长度为 1 的子数组开始合并，合并阶段中的每个子数组都是有序的。
public void MergeSort(int[] array)
{
    _Division(array, 0, array.Length - 1);
}

private void _Division(int[] array, int left, int right)
{
    if (left >= right)
    {
        return;
    }

var mid = (left + right) / 2;
    _Division(array, left, mid);
    _Division(array, mid + 1, right);
    if (right - left > 10)
    {
        __Merge(array, left, right, mid);
    }
    else
    {
        __Merge2(array, left, right, mid);
    }
}

private void __Merge(int[] array, int left, int right, int mid)
{
    // 初始化辅助数组
    var tmp = array[left..(right + 1)];
    var leftStart = 0;
    var leftEnd = mid - left;
    var rightStart = mid + 1 - left;
    var rightEnd = right - left;
    var k = leftStart;
    var j = rightStart;
    for (var i = left; i <= right; i++)
    {
        if (k > leftEnd)
        {
            array[i] = tmp[j++];
        }
        else if (j > rightEnd)
        {
            array[i] = tmp[k++];
        }
        else
        {
            if (tmp[k] > tmp[j])
            {
                array[i] = tmp[j++];
            }
            else
            {
                array[i] = tmp[k++];
            }
        }
    }
}

//可能时间复杂度高
private void __Merge2(int[] array, int left, int right, int mid)
{
    var j = right;
    //通过mid值和右端的值比较大小，如果mid值大于右端的值，则跟右端交换顺序，接着左端进行插入排序
    while (j > mid)
    {
        if (array[mid] > array[j])
        {
            (array[mid], array[j]) = (array[j], array[mid]);
            var midV = array[mid];
            var i = mid - 1;
            for (; i >= left; i--)
            {
                if (array[i] > midV)
                {
                    array[i + 1] = array[i];
                }
                else
                {
                    break;
                }
            }

array[i + 1] = midV;
        }

j--;
    }
}
```

---

-   堆排序

-   「堆 Heap」是一种满足特定条件的完全二叉树，可分为两种类型：`大顶堆 Max Heap」，任意节点的值>=其子节点的值；` `「小顶堆 Min Heap」，任意节点的值<=其子节点的值；`

-   优先队列的定义是具有出队优先级的队列，通常使用堆来实现

-   堆的常用操作及其对应的时间复杂度包括：元素入堆O(logn)、堆顶元素出堆O(logn)和访问堆顶元素O(1)等。

-   完全二叉树非常适合用数组表示，因此我们通常使用数组来存储堆。

-   堆化操作用于维护堆的性质，在入堆和出堆操作中都会用到。

-   输入n个元素并建堆的时间复杂度可以优化至O(n)，非常高效。

-   Top-K 是一个经典算法问题，可以使用堆数据结构高效解决，时间复杂度为O(nlogK)

---

```C#
// 1.输入数组并建立大顶堆。完成后，最大元素位于堆顶。
// 2.将堆顶元素（第一个元素）与堆底元素（最后一个元素）交换。完成交换后，堆的长度减1 
// ，已排序元素数量加 1。
// 3.从堆顶元素开始，从顶到底执行堆化操作（Sift Down）。完成堆化后，堆的性质得到修复。
// 4.循环执行第 2. 和 3. 步。循环n-1轮后，即可完成数组排序。
private int __Parent(int i)
{
    return (i - 1) / 2;
}

private int __Left(int i)
{
    return i * 2 + 1;
}

private int __Right(int i)
{
    return i * 2 + 2;
}

private void __ShiftDown(int i, int n, int[] array)
{
    while (true)
    {
        var left = __Left(i);
        var right = __Right(i);
        var max = i;
        if (left < n && array[left] > array[max])
        {
            max = left;
        }

if (right < n && array[right] > array[max])
        {
            max = right;
        }

if (max == i)
        {
            break;
        }

(array[i], array[max]) = (array[max], array[i]);
        i = max;
    }
}

public void HeapSort(int[] array)
{
    var size = array.Length;
    var p = __Parent(size - 1);
    //构建大顶堆
    for (var i = p; i >= 0; i--)
    {
        __ShiftDown(i, size, array);
    }

for (int i = size - 1; i > 0; i--)
    {
        (array[0], array[i]) = (array[i], array[0]);
        __ShiftDown(0, i, array);
    }
}
```

---

-   桶排序

「桶排序 BucketSort」是分治思想的一个典型应用。它通过设置一些具有大小顺序的桶，每个桶对应一个数据范围，将数据平均分配到各个桶中；然后，在每个桶内部分别执行排序；最终按照桶的顺序将所有数据合并。

桶排序(Bucket Sort)，总结：
桶排序，是一种复杂度为O(n+k)的排序
桶排序，是一种稳定的排序
桶排序，适用于数据均匀分布在一个区间内的场景

---

```C#
// 1.初始化k个桶，将n个元素分配到k个桶中；
// 2.对每个桶分别执行排序（本文采用编程语言的内置排序函数）；
// 3.按照桶的从小到大的顺序，合并结果；
// 桶排序适用于处理体量很大的数据。例如，输入数据包含 100 万个元素，
// 由于空间限制，系统内存无法一次性加载所有数据。
// 此时，可以将数据分成 1000 个桶，然后分别对每个桶进行排序，最后将结果合并。
/* 桶排序 */
void bucketSort(float[] nums) {
    // 初始化 k = n/2 个桶，预期向每个桶分配 2 个元素
    int k = nums.Length / 2;
    List<List<float>> buckets = new List<List<float>>();
    for (int i = 0; i < k; i++) {
        buckets.Add(new List<float>());
    }
    // 1. 将数组元素分配到各个桶中
    foreach (float num in nums) {
        // 输入数据范围 [0, 1)，使用 num * k 映射到索引范围 [0, k-1]
        int i = (int) (num * k);
        // 将 num 添加进桶 i
        buckets[i].Add(num);
    }
    // 2. 对各个桶执行排序
    foreach (List<float> bucket in buckets) {
        // 使用内置排序函数，也可以替换成其他排序算法
        bucket.Sort();
    }
    // 3. 遍历桶合并结果
    int j = 0;
    foreach (List<float> bucket in buckets) {
        foreach (float num in bucket) {
            nums[j++] = num;
        }
    }
}
```

---

-   计数排序
「计数排序 Counting Sort」通过统计元素数量来实现排序，通常应用于整数数组

---

```C#
// 1.遍历数组，找出数组中的最大数字，记为max，然后创建一个长度为max+1的辅助数组counter ；
// 2.借助counter统计nums中各数字的出现次数，其中counter[num]对应数字num的出现次数。统计方法很简单，
// 3.只需遍历num（设当前数字为 num），每轮将 counter[num] 增加即可。
// 由于counter的各个索引天然有序，因此相当于所有数字已经被排序好了。
// 4.接下来，我们遍历counter ，根据各数字的出现次数，将它们按从小到大的顺序填入nums即可。

// 计数排序只适用于非负整数。若想要将其用于其他类型的数据，需要确保这些数据可以被转换为非负整数，
// 并且在转换过程中不能改变各个元素之间的相对大小关系。例如，对于包含负数的整数数组，可以先给所有数字加上一个常数，
// 将全部数字转化为正数，排序完成后再转换回去即可。
//
// 计数排序适用于数据量大但数据范围较小的情况。比如，在上述示例中max不能太大，否则会占用过多空间。而当n<<max时，
// 计数排序使用O(max)时间，可能比O(nlogn)的排序算法还要慢
public void CountingSort(int[] array)
{
    if (array.Length < 2)
    {
        return;
    }

int max = array[0];
    for (var i = 1; i < array.Length; i++)
    {
        if (array[i] > max)
        {
            max = array[i];
        }
    }

var counting = new List<int>();
    for (var i = 0; i <= max; i++)
    {
        counting.Add(0);
    }

foreach (var t in array)
    {
        counting[t] += 1;
    }

var index = 0;
    for (var i = 0; i <= max; i++)
    {
        for (var j = 0; j < counting[i]; j++)
        {
            array[index++] = i;
        }
    }
}
```

---

-   基数排序
「基数排序 Radix Sort」的核心思想与计数排序一致，也通过统计个数来实现排序。在此基础上，基数排序利用数字各位之间的递进关系，依次对每一位进行排序，从而得到最终的排序结果。
在连续的排序轮次中，后一轮排序会覆盖前一轮排序的结果。举例来说，如果第一轮排序结果`a<b`，而第二轮排序结果 
`a>b`，那么第二轮的结果将取代第一轮的结果。由于数字的高位优先级高于低位，我们应该先排序低位再排序高位。

---

```C#
// 初始化位数k=1；
// 对学号的第k位执行「计数排序」。完成后，数据会根据第k位从小到大排序；
// 将k增加1，然后返回步骤 2. 继续迭代，直到所有位都排序完成后结束；
// 78/1 % =>>>>8
// 78/10 % 10 =>>>>7
private int __Digit(int num, int exp)
{
    return (num / exp) % 10;
}

private void __CountingSortDigit(int[] array, int exp)
{
    var counting = new int[10];

for (var i = 0; i < array.Length; i++)
    {
        var v = array[i];
        counting[__Digit(v, exp)] += 1;
    }

for (var i = 1; i < counting.Length; i++)
    {
        // 求前缀和，将“出现个数”转换为“数组索引”
        counting[i] += counting[i - 1];
    }

var res = new int [array.Length];
    for (int i = array.Length - 1; i >= 0; i--)
    {
        var v = array[i];
        var d = __Digit(v, exp);
        res[--counting[d]] = v;
    }

for (var i = 0; i < res.Length; i++)
    {
        array[i] = res[i];
    }
}

public void RadixSort(int[] array)
{
    if (array.Length < 2)
    {
        return;
    }

var max = array[0];
    for (var i = 1; i < array.Length; i++)
    {
        if (array[i] > max)
        {
            max = array[i];
        }
    }

for (var exp = 1; exp <= max; exp *= 10)
    {
        __CountingSortDigit(array, exp);
    }
}
```