数据结构：常见排序算法详解与代码实现

稳定排序与不稳定排序分类

稳定排序：冒泡排序、直接插入排序、归并排序 不稳定排序：快速排序、堆排序、选择排序、希尔排序

直接插入排序

实现思路

从第一个元素开始，默认第一个元素是有序的，将其之后的元素与前面的进行依次比较，根据条件进行移动、插入。

单趟实现

整体实现

//直接插入排序
void Direct(int* arr, int size) {
    assert(arr);
    for (int i = 1; i < size; i++) {
        //待比元素（待比元素刚开始应该在待排元素的前一位）
        int end = i - 1;
        //待排元素
        int tmp = arr[i];
        while (end >= 0) {
            //如果待排的比比较的元素小，就后移
            if (arr[end] > tmp) {
                arr[end + 1] = arr[end];
                end--;
            } else break;
        }
        //插入
        arr[end + 1] = tmp;
    }
}

复杂度

时间复杂度最坏：O(N^2)，空间复杂度：O(1)

希尔排序

实现思路

希尔排序是在直接插入排序上的优化，从大概有序到整体有序，避免了最坏情况。将一个数组分组，保证每组间隔一致，将每组进行直接插入排序，再整体实现直接插入排序。

单趟实现（注意待排元素不越界）

整体实现达到大概有序

再进行一趟直接插入排序达到整体有序

//希尔排序
void Shell(int* arr, int size) {
    assert(arr);
    //设置间隔
    int val = 3;
    for (int j = 0; j < val; j++) { //外出循环控制 end 的起始位置
        //单趟（内层循环控制 end、tmp 的位置）
        for (int i = j; i + val < size; i += val) {
            //待比元素
            int end = i;
            //待排元素
            int tmp = arr[end + val];
            while (end >= 0) {
                //如果待排元素小于待比元素就前移
                if (arr[end] > tmp) {
                    arr[end + val] = arr[end];
                    end -= val;
                } else break;
            }
            //循环结束代表满足插入条件
            arr[end + val] = tmp;
        }
    }
    Direct(arr, size);
}

代码优化

假如有一万个数据，那么间隔 val 就太短了不适合，我们可以让间隔为每次的二分之一，根据长度选择间隔。最后间隔会达到 1，同时也就不用去再接入直接插入排序的接口了。

复杂度

优化之前时间复杂度最坏情况：O(N^2) 优化之后明显感觉更效率：外层 * 内层 O(logN) * O(N) 空间复杂度：O(1)

堆排序

实现思路

利用堆的向上调整、向下调整来存储数据，再利用多次出堆顶元素来完成排序。下面小编用大顶堆、从下标 1 开始存储来实现堆排序。

实现堆：

//建推 Heap Heapspace;

//初始化
void Perliminary(Heap* Heapspace) {
    Heapspace->max = MAX;
    Heapspace->size = 0;
    Heapspace->data = (int*)malloc(sizeof(int) * Heapspace->max);
    if (Heapspace->data == NULL) {
        printf("初始化失败\n");
        return;
    }
}

//交换函数
void Exchange(int* p1, int* p2) {
    int tmp = *p1;
    *p1 = *p2;
    *p2 = tmp;
}

//上浮调整
void Upward(int* data, int child) {
    int parent = child / 2;
    while (parent > 0) {
        if (data[child] > data[parent]) {
            Exchange(&data[child], &data[parent]);
            child = parent;
            parent = child / 2;
        } else break;
    }
}

//入堆
void Enter(Heap* Heapspace, int data) {
    if (Heapspace->size == Heapspace->max) {
        int* pc = (int*)malloc(sizeof(int) * (Heapspace->max) * 2);
        if (pc == NULL) {
            printf("空间扩容失败\n");
            return;
        }
        Heapspace->max *= 2;
        Heapspace->data = pc;
    }
    Heapspace->size++;
    Heapspace->data[Heapspace->size] = data;
    Upward(Heapspace->data, Heapspace->size);
}

//打印堆元素
void Printf_Heap(Heap Heapspace, int size) {
    printf("堆元素：");
    for (int i = 1; i <= size; i++) {
        printf("%d ", Heapspace.data[i]);
    }
    printf("\n");
}

//下沉调整
void Subsidence(Heap* Heapspace) {
    int parent = 1;
    int child = 2 * parent;
    Exchange(&Heapspace->data[1], &Heapspace->data[Heapspace->size]);
    if (Heapspace->size > 1) {
        Heapspace->size--;
    }
    while (parent > 0 && child <= Heapspace->size) {
        if (child <= Heapspace->size && Heapspace->data[child] < Heapspace->data[child + 1]) {
            child++;
        }
        if (child <= Heapspace->size && Heapspace->data[parent] < Heapspace->data[child]) {
            Exchange(&Heapspace->data[parent], &Heapspace->data[child]);
            parent = child;
            child = 2 * parent;
        } else break;
    }
}

堆排序：利用堆的下沉调整，每次将堆尾元素与堆顶元素交换，然后调整堆以保持大顶堆的性质，多次调整达到排序效果。

for (int j = 0; j < size; j++) {
    Subsidence(&Heapspace);
}

复杂度

时间复杂度为 O(N logN)，空间复杂度为 O(1)

冒泡排序

实现思路

从第一个元素开始，与之后的所有元素进行比较，较大则交换位置，直至排完所有元素。

单趟实现：

整体实现：

//冒泡排序
void Bubbles(int* arr, int size) {
    assert(arr);
    for (int i = 1; i < size; i++) {
        for (int end = 0; end < size - 1; end++) {
            if (arr[end] > arr[end + 1]) {
                Exchange(&arr[end], &arr[end + 1]);
            }
        }
    }
}

代码优化

如果经过单趟，没有任何排序过程，说明整体都是有序的，可以直接结束循环。

复杂度

时间复杂度：O(N^2)，空间复杂度：O(1)

选择排序

实现思路

开始整个数组都是无序的，找整个无序组中的最小值，与有序部分的末尾进行交换，一直重复。

单趟实现：

整体实现：

//选择排序
void Select(int* arr, int size) {
    assert(arr);
    int end = 0;
    int tmp = 0;
    for (int i = 0; i < size - 1; i++) {
        tmp = end;
        for (int j = end; j < size; j++) {
            if (arr[j] < arr[tmp]) {
                tmp = j;
            }
        }
        Exchange(&arr[tmp], &arr[end]);
        end++;
    }
}

复杂度

时间复杂度：O(N^2)，空间复杂度：O(1)

Hoare 排序

实现思路

通过两个指针的移动，左边找大，右边找小，目的是让大的去到右边，小的去到左边，二者相遇再与 key 位置交换。记得 key 在哪边，对面的指针先动。

单趟实现：左边找大，右边找小，相遇则交换 key 的位置元素。

整体实现：此时需要更新 key 的位置到二者相遇的位置，然后就将数组分为了两组，分别递归。

记录的原因以及递归的过程：如果不记录 left、right，那么递归右区间时，right 会随着左递归不断变化，导致无法递归右区间。

//Hoare 排序
void Hoare(int* arr, int left, int right, int size) {
    if (left >= right) {
        return;
    }
    int begin = left;
    int end = right;
    int key = left;
    while (left < right) {
        while (arr[right] >= arr[key] && left < right) {
            right--;
        }
        while (arr[left] <= arr[key] && left < right) {
            left++;
        }
        Exchange(&arr[left], &arr[right]);
    }
    Exchange(&arr[key], &arr[left]);
    key = left;
    Hoare(arr, begin, key - 1, size);
    Hoare(arr, key + 1, end, size);
}

复杂度

时间复杂度：O(N logN)，空间复杂度：O(1)

快排（双指针）

实现思路

单趟：开始时有两个指针 prev 与 cur，分别找大找小，随后进行交换。注意交换完之后，cur 需要移动，否则一直进不了循环。

整体实现：现在我们划分了基准值，分别递归左、右区间，注意记录部分值，原因和 Hoare 排序一样。

//快排（双指针）
void Snap_shot(int* arr, int size, int prev) {
    assert(arr);
    int cur = prev + 1;
    if (cur >= size) {
        return;
    }
    int begin = prev;
    int pivot = prev;
    while (cur < size) {
        while (arr[cur] >= arr[pivot] && cur < size) {
            cur++;
        }
        while (arr[prev] <= arr[pivot] && prev < cur && cur < size) {
            prev++;
        }
        if (cur < size) {
            Exchange(&arr[cur], &arr[prev]);
            cur++;
        }
    }
    Exchange(&arr[prev], &arr[pivot]);
    pivot = prev;
    Snap_shot(arr, pivot, begin);
    Snap_shot(arr, size, pivot + 1);
}

复杂度

时间复杂度：O(N logN)，空间复杂度：O(1)

归并排序

实现思路

首先咱们看到这是将一个数组每次递归二分，这里通过划分区间并不难，难的是合并时如何排序？建议一个临时数组，通过每次函数返回的基准值进行划分区间，当划分到左右区间只有一个数据时开始合并，合并时就需要去排序了。

递归分组：左区间不断随着 Middle 分半，右区间会随着左区间传的参数改变 left、right 来产生，右边同理。

if (left >= right) {
    return;
}
int Middle = (left + right) / 2;
Sort(arr, newnode, left, Middle);
Sort(arr, newnode, Middle + 1, right);

归并过程：此时我们划分了左右区间，分别是...然后我们对这个区间进行排序，排序的结果先放在临时数组。

我们可以用 memcpy 一键拷贝，需要注意它的三个参数：目的地起始位置、源起始位置、字节。

主函数：

//归并排序
void Merge(int* arr, int size) {
    assert(arr);
    int* newnode = (int*)malloc(sizeof(int) * size);
    if (newnode == NULL) {
        printf("空间开辟失败\n");
        return;
    }
    Sort(arr, newnode, 0, size - 1);
}

子函数（递归、合并函数）：

//归并子函数
void Sort(int* arr, int* newnode, int left, int right) {
    if (left >= right) {
        return;
    }
    int Middle = (left + right) / 2;
    Sort(arr, newnode, left, Middle);
    Sort(arr, newnode, Middle + 1, right);
    int begin1 = left;
    int end1 = Middle;
    int begin2 = Middle + 1;
    int end2 = right;
    int tmp = left;
    while (begin1 <= end1 && begin2 <= end2) {
        if (arr[begin1] < arr[begin2]) {
            newnode[tmp] = arr[begin1];
            begin1++;
            tmp++;
        } else {
            newnode[tmp] = arr[begin2];
            begin2++;
            tmp++;
        }
    }
    while (begin1 <= end1) {
        newnode[tmp] = arr[begin1];
        begin1++;
        tmp++;
    }
    while (begin2 <= end2) {
        newnode[tmp] = arr[begin2];
        begin2++;
        tmp++;
    }
    memcpy(arr + left, newnode + left, sizeof(int) * (right - left + 1));
}

复杂度

时间复杂度：O(N logN)，空间复杂度：O(N)

排序 OJ 题（1）

快排采用找基准值，划分区间进行递归排序，为分治思想。

排序 OJ（2）

注意是从后往前比较。 假设此时排序完前 7 个元素：15、23、38、54、60、72、96 现在将 45 插入其中 45 VS 96 继续比较直到比到 38, 45>38，停止比较，中间有 4 个元素加上 38 一共比较了 5 次 此题何为从后往前：例如第一个 54 已经为有序，现在插入 38 38<54，有序组变为 38、54，继续下一个元素，意思是前 7 个正常排，45 采用从后往前排

排序 OJ（3）

归并需要额外开辟一个数组作为临时数组。

排序 OJ（4）

稳定排序的有：冒泡、直接插入、归并 时间复杂度稳定在 O(N^2) 的只有直接插入排序

排序 OJ（5）

两个指针分别找大找小再交换、最后找大的指针指向的元素与基准值 65 交换，得到 A