排序

排序是生活中常常会遇到的问题，也是面试中经常会问的算法，本文简单记录了常见的排序算法，使用C++与Python分别实现。

稳定性

将设ki = kj ( 1 <= i < j <=n )，在序列中的位置ri 领先于 rj，如果排序后 ri依旧领先于 rj，则成为算法是稳定的，反之，如果可能使得排序后的序列中 rj 领先于ri，则称排序为不稳定的。

排序的种类

代码用到公用函数

c++

//utils.h
#include<random>
#include<ctime>
#include<vector>
#include<iostream>

typedef std::vector<int> IntArray;
typedef IntArray::iterator ArrayIter;

void GetRandomArray(IntArray &array, int min, int max, uint32_t size);
int GetRandom(int min, int max);
void PrintArray(const IntArray &array);
void swap(ArrayIter val1, ArrayIter val2);
void swap(int &a, int &b);

//utils.cc
#include "utils.h"

int GetRandom(int min, int max)
{
    srand(clock());
    int interval = max - min;
    int random = rand() % interval;

    return random + min;
}   

void GetRandomArray(IntArray &array, int min, int max, uint32_t size){
    while(size--){
        array.push_back(GetRandom(min, max));
    }
}

void PrintArray(const IntArray &array)
{
    const int ROW_NUM = 20;
    const int WIDTH = 8;
    int row_index = 0;   
    for (IntArray::const_iterator iter = array.begin(); iter != array.end(); iter++)
    {
        std::cout.setf(std::ios::left);
        std::cout.width(WIDTH);
        std::cout << *iter;
        row_index ++;
        if(row_index == ROW_NUM){
            std::cout << std::endl;
            row_index = 0;
        }   
    }
    std::cout << std::endl;
}

void swap(ArrayIter val1, ArrayIter val2){
    int temp = *val1;
    *val1 = *val2;
    *val2 = temp;
}

void swap(int &a, int &b)
{
    int temp = a;
    a = b;
    b = temp;
}

python

import random

CONST_ROW_NUM = 10

def get_random(min, max, num):
    return [int(random.random()*(max-min) + min) for i in range(num)]

def print_nums(nums):
    for i in range(len(nums)):
        if i!=0 and i%CONST_ROW_NUM == 0:
            print()
        print("%-10d"%(nums[i]), end="")

    print()

冒泡排序

两两比较相邻记录，若反序则交换，直到没有反序的记录为止。

冒泡排序的过程

从图中可以看到，每一轮比较可以得到待比较序列的最大值，每次将最大值往上移动后，对剩下的序列进行冒泡排序，最终可以得到有序序列。

c++

#include <iostream>

#include "utils.h"

using namespace std;

void BubbleSort(IntArray &data)
{
    bool sort_flag = true;

    for (ArrayIter out_iter = data.begin(); out_iter != data.end() && sort_flag; out_iter++)
    {
        sort_flag = false;
        for (ArrayIter in_iter = data.end() - 1; in_iter > out_iter; in_iter--)
        {
            if(*in_iter < *(in_iter - 1)){
                sort_flag = true;           //优化，如果没有走到这一步，那么序列现在已经有序，无需在进行下去
                int temp = *in_iter;
                *in_iter = *(in_iter - 1);
                *(in_iter - 1) = temp;
            }
        }
    }
}

int main(int argc, char const *argv[])
{
    IntArray data;
    GetRandomArray(data, 0, 100, 10);
    cout << "Raw input:" << endl;;
    PrintArray(data);

    BubbleSort(data);

    cout << "Result output:"<<endl;
    PrintArray(data);

    return 0;
}

python

import utils 

def bubble_sort(nums):
    sort_flag = True

    for i in range(len(nums) - 1):
        sort_flag = False
        for j in range(len(nums)-1, i, -1):
            if nums[j] < nums[j-1]:
                sort_flag = True
                nums[j],nums[j-1] = nums[j-1],nums[j]

        if not sort_flag:
            break
def main():
    nums = utils.get_random(0,100,10)
    print("Raw input:")
    utils.print_nums(nums)
    bubble_sort(nums)
    print("Result output:")
    utils.print_nums(nums)

if __name__ == "__main__":
    main()

时间复杂度

最坏情况下，即序列是逆序的，需要进行1+2+3+...+n=n(n-1)/2次比较，并做同等数量的移动，因此，总的时间复杂度为o(n^2)。

选择排序

通过n-i次的比较，从n-i+1序列中选择最小（最大）的元素，并和第i个记录进行交换。

选择排序的过程

c++

#include <iostream>

#include "utils.h"

using namespace std;

void SelectSort(IntArray &data)
{
    for (ArrayIter out_iter = data.begin(); out_iter != data.end(); out_iter++)
    {
        ArrayIter min_iter = out_iter;
        for (ArrayIter in_iter = out_iter + 1; in_iter != data.end(); in_iter++)
        {
            if (*min_iter > *(in_iter))
            {
                min_iter = in_iter;
            }
        }

        if (min_iter != out_iter)
        {
            swap(min_iter, out_iter);
        }
    }
}

int main(int argc, char const *argv[])
{
    IntArray data;
    GetRandomArray(data, 0, 100, 10);
    cout << "Raw input:" << endl;
    PrintArray(data);

    SelectSort(data);

    cout << "Result output:" << endl;
    PrintArray(data);

    return 0;
}

python

import utils

def select_sort(nums):
    for i in range(len(nums) - 1):
        min_index = i
        for j in range(i+1, len(nums)):
            if nums[min_index] > nums[j]:
                min_index = j

        if min_index != i:
            nums[min_index], nums[i] = nums[i], nums[min_index]

def main():
    nums = utils.get_random(0,100,10)
    print("Raw input:")
    utils.print_nums(nums)
    select_sort(nums)
    print("Result output:")
    utils.print_nums(nums)

if __name__ == "__main__":
    main()

时间复杂度

选择排序无论最好还是最坏的情况下，其比较次数一样多，第i趟排序需要n-i次比较，因此需要比较n-1+n-2+...+1 = n(n-1)/2次，对于交换次数，最好情况下，交换0次，最坏情况下交换n-1次，因此总的时间复杂度仍然是O(n^2)。

直接插入排序

将一个记录插入到已排序的序列当中。

直接插入排序的过程

c++

#include <iostream>
#include <limits>

#include "utils.h"

using namespace std;

void InsertSort(IntArray &data)
{
    IntArray temp;
    for (ArrayIter input_iter = data.begin(); input_iter != data.end(); input_iter++)
    {
        if (temp.empty() || *input_iter > temp.back())
        {
            temp.push_back(*input_iter);
        }
        else
        {
            temp.push_back(INT_MIN);
            ArrayIter output_iter;
            // 终止条件比较复杂
            for (output_iter = temp.end() - 1; *(output_iter - 1) > *input_iter && output_iter > temp.begin(); output_iter--)
            {
                *(output_iter) = *(output_iter-1);
            }

            *output_iter = *input_iter;
        }
    }
    data = temp;
}

int main(int argc, char const *argv[])
{
    IntArray data;
    GetRandomArray(data, 0, 100, 10);
    cout << "Raw input:" << endl;
    PrintArray(data);

    InsertSort(data);

    cout << "Result output:" << endl;
    PrintArray(data);

    return 0;
}

python

import utils

def insert_sort(nums):
    temp = []
    for num in nums:
        if len(temp) == 0 or num > temp[-1]:
            temp.append(num)
        else:
            temp.append(num)
            i = len(temp) - 2
            while temp[i] > num and i > -1:
                temp[i+1] = temp[i]
                i -= 1
            temp[i+1] = num

    for i in range(len(nums)):
        nums[i] = temp[i]

def main():
    nums = utils.get_random(0,100,10)
    print("Raw input:")
    nums= [2,0,2,1,1,0]
    utils.print_nums(nums)
    insert_sort(nums)
    print("Result output:")
    utils.print_nums(nums)

if __name__ == "__main__":
    main()

时间复杂度

最好情况下，即序列本身是有序的，无需移动，只需比较n次，因此时间复杂度为O(n)；最坏情况下，即序列本身是逆序的，因此需要比较 2 + 3 + 4 + ... + n = (n+2)(n-1)/2次，记录的移动次数也达到最大值(n+4)(n-1)/2次，因此最大时间复杂度为O(n^2)；平均时间复杂度约为n^2/4。

堆排序

堆是具有下列性质的完全二叉树，每个节点的值都大于或等于其左右孩子节点的值，成为大顶堆；或者每个几点的值小于或等于其左右孩子节点的值，称为小顶堆。
堆排序的具体过程为，将待排序的序列构成一个大顶堆，此时根节点一定是最大值，将根节点与尾节点进行交换，然后将剩余的n-1个序列重新构成一个堆，这样就可以得到n个元素中的次大值，如此反复执行，最后就构成一个有序序列。

堆排序过程

c++

#include <iostream>

#include "utils.h"

using namespace std;

void BuildSort(IntArray &data, int index, int len)
{
    //置顶向下调整
    for (int i = index; i < data.size();)
    {
        int left_child_index = 2 * i + 1;
        int max_child_index = left_child_index;

        if (left_child_index >= len)
        {
            //无子节点
            break;
        }

        if (left_child_index + 1 < len && data[left_child_index + 1] > data[left_child_index])
        {
            max_child_index = left_child_index + 1;
        }

        if (data[i] > data[left_child_index])
        {
            //接下去的不用调整了
            break;
        }
        else
        {
            //交换
            int temp = data[max_child_index];
            data[max_child_index] = data[i];
            data[i] = temp;
        }
        i = max_child_index;
    }
}

void HeapSort(IntArray &data)
{
    for (int i = data.size() / 2 - 1; i >= 0; i--)
    {
        BuildSort(data, i, data.size());
    }

    for (int i = data.size(); i > 0; i--)
    {

        swap(data[0], data[i - 1]);
        BuildSort(data, 0, i - 1); //是i-1而不是i
    }
}

int main(int argc, char const *argv[])
{
    IntArray data;
    GetRandomArray(data, 0, 100, 100);
    cout << "Raw input:" << endl;

    PrintArray(data);

    HeapSort(data);

    cout << "Result output:" << endl;
    PrintArray(data);

    return 0;
}

python

import utils

#从heap_index往下重建堆
def build_heap(nums, heap_index, end):
    while heap_index <=end:

        left_index = 2 * heap_index + 1
        right_index = 2 * heap_index + 2
        max_child_index = left_index
        
        #到堆底
        if left_index > end:  
            return 

        if right_index <= end and nums[right_index] > nums[left_index]:
            max_child_index = right_index

        if nums[max_child_index] <= nums[heap_index]:
            return 

        nums[heap_index],nums[max_child_index] = nums[max_child_index],nums[heap_index]
        heap_index = max_child_index
        
def heap_sort(nums):
    for heap_index in range(int(len(nums)/2) - 1, -1, -1):
        # 初始重建需要从下往上建立
        build_heap(nums, heap_index, len(nums) - 1)

    for i in range(len(nums)-1, 0, -1):
        nums[i], nums[0] = nums[0], nums[i]
        #调整
        build_heap(nums, 0, i-1)

def main():
    nums = utils.get_random(0,100,10)
    print("Raw input:")
    utils.print_nums(nums)
    heap_sort(nums)
    print("Result output:")
    utils.print_nums(nums)

if __name__ == "__main__":
    main()

时间复杂度

构建堆的时间复杂度为O(n)，每次重建对堆的需要用O(logn)，需要取n-1次堆顶记录，因此时间复杂度为O(nlongn)。

归并排序

假设初始序列有n个记录，则可以看成是有n个有序的子序列，每个子序列的长度为1，然后两两归并，得到[n/2]个长度为2或为1的子序列，然后再两两归并，如此重复，直到一个长度为n的有序序列位置，这种成为2路归并排序。

递归的归并排序 非归并排序的过程

c++

//递归版
#include <iostream>
#include <vector>

#include "utils.h"

using namespace std;

void Merge(IntArray::iterator iter, uint32_t left, uint32_t mid, uint32_t right)
{
    IntArray temp_array;
    uint32_t left_index = left, right_index = mid + 1;
    //比较
    while (left_index <= mid && right_index <= right)
    {
        if (*(iter + left_index) < *(iter + right_index))
        {
            temp_array.push_back(*(iter + left_index));
            left_index++;
        }
        else
        {
            temp_array.push_back(*(iter + right_index));
            right_index++;
        }
    }
    //将剩余的复制过去
    while (left_index <= mid)
    {
        temp_array.push_back(*(iter + (left_index++)));
    }
    //将剩余的复制过去
    while (right_index <= right)
    {
        temp_array.push_back(*(iter + (right_index++)));
    }
    //注意坐标的变化
    int begin_index = 0;
    while (begin_index + left <= right)
    {
        *(iter + left + begin_index) = temp_array[begin_index];
        begin_index++;
    }
}

void _MergeSort(IntArray::iterator iter, uint32_t left, uint32_t right)
{
    if (left == right)
    {
        return;
    }

    uint32_t mid = (right + left) / 2;

    _MergeSort(iter, left, mid); //递归归并排序
    _MergeSort(iter, mid + 1, right);
    Merge(iter, left, mid, right); //合并
    return;
}

void MergeSort(IntArray &input_data)
{
    _MergeSort(input_data.begin(), 0, input_data.size() - 1);
}

int main(int argc, char const *argv[])
{
    const uint32_t TEST_NUM_COUNT = 10;
    const int MIN_NUM = 0;
    const int MAX_NUM = 100;

    IntArray input_data;
    GetRandomArray(input_data, MIN_NUM, MAX_NUM, TEST_NUM_COUNT);
    cout << "Raw input:" << endl;
    PrintArray(input_data);

    MergeSort(input_data);

    cout << "Raw input:" << endl;
    PrintArray(input_data);

    return 0;
}

//非递归版
#include <iostream>
#include <unistd.h>
#include "utils.h"

using namespace std;

//合并子序列
void Merge(IntArray &input, IntArray &output, int left, int mid, int right)
{
    int left_index = left, right_index = mid + 1;
    int start_index = left;

    while (left_index <= mid && right_index <= right)
    {
        if (input[left_index] < input[right_index])
        {
            output[start_index++] = input[left_index];
            left_index++;
        }
        else
        {
            output[start_index++] = input[right_index];
            right_index++;
        }
    }
    while (left_index <= mid)
    {
        output[start_index++] = input[left_index];
        left_index++;
    }

    while (right_index <= right)
    {
        output[start_index++] = input[right_index];
        right_index++;
    }
}

void MergeSort(IntArray &input)
{
    int len = (int32_t)(input.size());      //转化为有符号整型，防止下面计算的时候负数变为正整数（len-2*k -1） 
    IntArray output(input.size(), 0);
    //k表示合并的子序列长度，大于len就无意义了，每次以2的倍数增长
    for (int k = 1; k < len; k *= 2)      
    {
        int l = 0;
        //序号0开始， 一直到要合并的第二对合并子序列，因为最后一对可能长度不够，因此终止条件为  len-1 - 2*k
        //如果恰好最后一对也是两个k序列，那么  刚刚len-1-2*k +2*k 为最后一个序号
        for (l = 0; l <= len  - 2 * k - 1; l += 2 * k)
        {
            Merge(input, output, l,  l + k - 1  , l+2*k - 1 );
        }
        //l是最后一对要合并的序列的起始序号，如果剩余的序列长度>k要合并，否则不需要合并
        if(len - l >= k)
        {
            Merge(input, output, l, l + k - 1, len - 1);
        }
        input = output;
    }
}                          
int main(int argc, char const *argv[])
{
    IntArray input_data, output_data;
    GetRandomArray(input_data, 0, 100, 10);
    cout << "Raw input:" << endl;

    PrintArray(input_data);

    MergeSort(input_data);

    cout << "Result output:" << endl;
    PrintArray(input_data);

    return 0;

    return 0;
}

python

#非递归
import utils 

def _merge(nums, left, mid, right):
    temp = []
    left_index = left
    right_index = mid+1

    while left_index <= mid and right_index <= right:
        if nums[left_index] <= nums[right_index]:
            temp.append(nums[left_index])
            left_index += 1
        else:
            temp.append(nums[right_index])
            right_index += 1

    while left_index <= mid:
        temp.append(nums[left_index])
        left_index += 1

    while right_index <= right:
        temp.append(nums[right_index])
        right_index += 1

    for index,num in enumerate(temp):
        nums[left + index] = num

def _merge_sort(nums, left, right):
    if left == right:
        return

    mid = int((left+right) / 2)

    _merge_sort(nums, left, mid)
    _merge_sort(nums, mid+1, right)
    _merge(nums, left, mid, right)

def merge_sort(nums):
    _merge_sort(nums, 0, len(nums)-1)

def main():
    nums = utils.get_random(0,100,10)
    print("Raw input:")
    utils.print_nums(nums)
    merge_sort(nums)
    print("Result output:")
    utils.print_nums(nums)

if __name__ == "__main__":
    main()

#非递归
import utils

def _merge(nums, left, mid, right):
    temp = []
    left_index = left
    right_index = mid+1

    while left_index <= mid and right_index <= right:
        if nums[left_index] <= nums[right_index]:
            temp.append(nums[left_index])
            left_index += 1
        else:
            temp.append(nums[right_index])
            right_index += 1

    while left_index <= mid:
        temp.append(nums[left_index])
        left_index += 1

    while right_index <= right:
        temp.append(nums[right_index])
        right_index += 1

    for index,num in enumerate(temp):
        nums[left + index] = num

def merge_sort(nums):
    k = 1      #子序列大小从1开始
    while k < len(nums):
        
        start = 0

        while start <= len(nums) - 2*k :
            _merge(nums, start, start + k - 1, start + 2*k -1)
            start += 2*k
        #剩余长度不足2k长度的序列
        if len(nums) > start + k:
            _merge(nums, start, start + k -1, len(nums) - 1)

        k *= 2  #每次扩大到原来的2倍

def main():
    nums = utils.get_random(0,100,10)
    nums = [0,0,1,1,2,2]
    print("Raw input:")
    utils.print_nums(nums)
    merge_sort(nums)
    print("Result output:")
    utils.print_nums(nums)

if __name__ == "__main__":
    main()

快速排序

对于一个顺序的序列来说，对于其中的每一个数字，它左边的数字总是小于或等于它，它右边的数字总是大于或等于它，根据这个思想，提出了快速排序的概念。
基本思想是通过一趟排序将待排序的记录分割成独立的两部分，其中一部分记录的关键字比另一个部分的关键字小，则可分别对这两部分记录进行排序，已达到整体有序的目的。

快速排序的过程

c++

#include <iostream>

#include "utils.h"
using namespace std;

void Partition(IntArray &input, int low, int high, int &partition_index)
{
    int key = input[low];

    while (low < high)
    {
        //找到右侧小于key的值
        while (low < high && input[high] > key)
        {
            high--;
        }
        //移动到左边
        if (low < high)
        {
            int temp = input[low];
            input[low] = input[high];
            input[high] = temp;
        }
        //寻找左边大于key 的值
        while (low < high && input[low] <= key)
        {
            low++;
        }
        //移动到右边
        if (low < high)
        {
            int temp = input[low];
            input[low] = input[high];
            input[high] = temp;
        }
        //low~hight又是跟初始状态一样，再继续寻找
    }

    partition_index = low;
}

void QSort(IntArray &input, int low, int high)
{
    if (low >= high)
    {
        return;
    }

    int partition_index = -1;
    /*
    原理：元素在排序中所在的位置，之前的元素都比该元素小，之后的元素都比该元素大
    因此快排的原理就是寻找位置，使得之前的元素比该值小，之后的元素比该值大
    */
    Partition(input, low, high, partition_index);
    QSort(input, low, partition_index - 1);
    QSort(input, partition_index + 1, high);
}

void QuickSort(IntArray &input_data)
{
    int low = 0;
    int high = input_data.size() - 1;

    QSort(input_data, low, high);
}

int main(int argc, char const *argv[])
{
    IntArray input_data, output_data;
    GetRandomArray(input_data, 0, 100, 10);
    cout << "Raw input:" << endl;

    PrintArray(input_data);

    QuickSort(input_data);

    cout << "Result output:" << endl;
    PrintArray(input_data);

    return 0;

    return 0;
}

python

import utils
import time

def _partitions(nums, low, high):
    key = nums[low]

    while low < high:
        while low < high and nums[high] >= key:
            high -= 1

        if low < high:
            nums[low] = nums[high]

        while low < high and nums[low] <= key:
            low += 1

        if low < high:
            nums[high] = nums[low]

    nums[low] = key
    return low

def _quick_sort(nums, low, high):
    if low >= high:    #条件为大于或等于
        return 
    partition_index = _partitions(nums, low, high)
    _quick_sort(nums, low, partition_index)
    _quick_sort(nums, partition_index+1, high)

def quick_sort(nums):
    _quick_sort(nums, 0, len(nums) - 1 )

def main():
    nums = utils.get_random(0,100,10)
    print("Raw input:")
    utils.print_nums(nums)
    quick_sort(nums)
    print("Result output:")
    utils.print_nums(nums)

if __name__ == "__main__":
    main()

总结

排序方法	平均复杂度	最好情况	最坏情况	辅助空间	稳定性
冒泡	O(n^2)	O(n)	O(n^2)	O(1)	稳定
选择排序	O(n^2)	O(n^2)	(n^2)	O(1)	稳定
插入排序	O(n^2)	O(n)	O(n^2)	O(n)	稳定
堆排序	O(nlogn)~O(n^2)	O(n^1.3)	O(n^2)	O(1)	不稳定
归并排序	O(nlogn)	O(nlogn)	O(nlogn)	O(n)	O(n) 不稳定
快速排序	O(nlogn)	O(nlogn)	O(n^2)	O(logn)~O(n)	不稳定