排序

算法

交换

void swap(int array[], int i, int j)
{
    int temp = array[i];
    array[i] = array[j];
    array[j] = temp;
}

冒泡排序
从后往前，相邻元素比较交换，每遍历一次，当前最小值归位。
时间复杂度：O(n²)。

void BubbleSort(int array[], int n)
{
    bool flag = true;
    for (int i = 0; i < n - 1 && flag; i++)
    {
        flag = false;
        for (int j = n - 1; j > i; j--)
        {
            if (array[j - 1] > array[j]) {
                swap(array, j, j - 1);
                flag = true;
            }
        }
    }
}

简单选择排序
寻找当前最小值放在前面。
时间复杂度：O(n²)。

void SelectSort(int array[], int n)
{
    int min;
    for (int i = 0; i < n - 1; i++)
    {
        min = i;
        for (int j = i + 1; j <= n - 1; j++)
        {
            if (array[min] > array[j])
                min = j;
        }
        if (min != i)
            swap(array, min, i);
    }
}

直接插入排序
将后面的值插入到前面已排序的序列中。
时间复杂度：O(n²)。

void InsertSort(int array[], int n)
{
    int i, j, key;
    for (i = 1; i < n; i++) {
        if (array[i] < array[i - 1]) {
            key = array[i];
            for (j = i - 1; array[j] > key; j--)
                array[j + 1] = array[j];
            array[j + 1] = key;
        }
    }
}

希尔排序
部分有序。
时间复杂度：O(n^2/3)。

void ShellSort(int array[], int n) {
    int i, j, key;
    int increment = n-1;
    do {
        increment = increment / 3+1;
        for (i = increment+1; i < n; i++) {
            if (array[i] < array[i - increment]) {
                key = array[i];
                for (j = i - increment; j >= 0 && key < array[j]; j -= increment)
                    array[j + increment] = array[j];
                array[j + increment] = key;
            }
        }
    }
    while (increment > 1);
}

归并排序

时间复杂度：O(nlogn)。

void merge(int *data, int start, int end, int *result)
{
    int left_length = (end - start + 1) / 2 + 1;//左部分区间的数据元素的个数
    int left_index = start;
    int right_index = start + left_length;
    int result_index = start;
    while (left_index < start + left_length && right_index < end + 1)
    {
        //对分别已经排好序的左区间和右区间进行合并
        if (data[left_index] <= data[right_index])
            result[result_index++] = data[left_index++];
        else
            result[result_index++] = data[right_index++];
    }
    while (left_index < start + left_length)
        result[result_index++] = data[left_index++];
    while (right_index < end + 1)
        result[result_index++] = data[right_index++];
}
void merge_sort(int *data, int start, int end, int *result)
{
    if (1 == end - start)//如果区间中只有两个元素，则对这两个元素进行排序
    {
        if (data[start] > data[end])
        {
            int temp = data[start];
            data[start] = data[end];
            data[end] = temp;
        }
        return;
    }
    else if (0 == end - start)//如果只有一个元素，则不用排序
        return;
    else
    {
        //继续划分子区间，分别对左右子区间进行排序
        merge_sort(data, start, (end - start + 1) / 2 + start, result);
        merge_sort(data, (end - start + 1) / 2 + start + 1, end, result);
        //开始归并已经排好序的start到end之间的数据
        merge(data, start, end, result);
        //把排序后的区间数据复制到原始数据中去
        for (int i = start; i <= end; ++i)
            data[i] = result[i];
    }
}

快速排序

时间复杂度：O(nlogn)。

int Partition(int array[], int low, int high) {
    int pivotkey;
    pivotkey = array[low];
    while (low < high) {
        while (low < high&&array[high] >= pivotkey)
            high--;
        swap(array, low, high);
        while (low < high&&array[low] <= pivotkey)
            low++;
        swap(array, low, high);
    }
    return low;
}
void QSort(int array[], int low, int high)
{
    int pivot;
    if (low < high) {
        pivot = Partition(array, low, high);
        QSort(array, low, pivot-1);
        QSort(array, pivot + 1, high);
    }
}