排序算法

插入排序(直接插入排序、折半插入排序、希尔排序)

一起学习

插入排序

直接插入排序

逻辑简述：

打扑克牌一张一张抓牌排序的原理

拿起一张，插入到手牌中合适的位置

#include<stdio.h>

#define SIZE 13

/**
 * 直接插入排序
 * @param a
 * @param size
 */
void directInsertSort(int *a, int size) {
    int j, k, tmp;

    //循环遍历整个数组
    for (int i = 0; i < size; ++i) {

        //遍历手牌 j = i - 1 ~ 0 ,i是现在摸的牌待插入的
        for (j = i - 1; j >= 0; --j) {//这里的j设计！！
            //待插入的牌大于手牌就保留位置退出
            //这里的保留位置体现在j是作用域
            if (a[i] > a[j])//a[i]是待插入的牌
                break;
        }

//        获取了待插入的空位，由于是--j，所以后续插入要+1
//        printf("j = %d\n",j);

        //插入
        //判断是不是最后一位数，是的话就不用插入了
        //也就是如果待插入的手牌都大于排序好的手牌中最后一位了，那就不用动了
        if (j != i - 1) {
            //遍历手牌
            tmp = a[i];//保存待插入的手牌
            //向后移动
            //为什么不是k >= j，因为j在上次退出for循环时--了
            for (k = i - 1; k >= j+1; --k) {//for只能保证k在for中>j
                //向后移动
                a[k + 1] = a[k];
//                printf("k = %d\n",k);
            }
            //找到之前需要插入的位置
            a[j + 1] = tmp;
        }

//        for (int i = 0; i < 13; ++i) {
//            printf("%d ", a2[i]);
//        }
//        printf("\n");
    }

    //遍历输出
    for (int i = 0; i < size; ++i) {
        printf("%d ", a[i]);
    }
}

int main(int argc, char *argv[]) {
    int a[SIZE] = {23, 4, 56, 7, 8, 9, 8, 76, 5, 4, 34, 5, 6};
    
//    直接插入排序
    printf("直接插入排序:\n");
    directInsertSort(a, SIZE);
    printf("\n");
}

设计的难点：

找手牌

for (j = i - 1; j >= 0; --j) {     
   if (a[i] > a[j])
     break;
}

确定位置j+1

向后挪动

for (k = i - 1; k > j; --k) {
   a[k + 1] = a[k];
}

插入

a[j + 1] = tmp;

Go实现

package main

import "fmt"

//定义一个待排序的数组
var a1 = [13]int{23, 94, 6, 92, 6, 5, 9, 3, 2, 59, 8, 1, 2}

func directInsertSort(a *[len(a1)]int, size int) {

	var j, k, tmp int

	//整体遍历循环
	for i := 0; i <= size-1; i++ {
		//线性查找待排序的位置
		for j = i - 1; j >= 0; j-- {
			if a[i] > a[j] {
				break
			}
		}

		//待插入的位置是 j+1

		//向后移动
		if j != i-1 { //待牌 < 所有的手牌就需向后移动
			//保存手牌,避免移动时被覆盖
			tmp = a[i]
			//向后移动
			for k = i - 1; k >= j+1; k-- {
				a[k+1] = a[k]
			}

			//插入
			a[j+1] = tmp
		}
	}

	for _, v := range a {
		fmt.Printf("%d ", v)
	}
}

func main() {
	directInsertSort(&a1, len(a1))
}

1 2 2 3 5 6 6 8 9 23 59 92 94

折半插入排序

在直接插入上做了优化，查找需要插入的位置时，用了二分查找(原先时线性查找)

#include<stdio.h>

#define SIZE 13

/**
 * 折半插入
 * @param a
 * @param size
 */
void halfInsertSort(int *a, int size, int v) {
    int left = 0;
    int right = size - 1;
    int mid;

    //1.二分查找
    while (left <= right) {
        mid = (left + right) / 2;

        if (v > a[mid]){
            left = mid + 1;
        } else{
            right = mid -1;
        }
    }
//  分许二分查找结束后需要插入的位置，见后图
//  right+1就是v要插入的位置,因为right会多减少一次

    //2.向后挪
    for (int i = size-1; i >= right+1; --i) {
        a[i+1] = a[i];
    }

    a[right+1] = v;
}

/**
 * 折半查找的入口函数
 * @param a 
 * @param size 
 */
void Main_halfInsertSort(int *a, int size){
    for (int i = 0; i < SIZE; ++i) {
        halfInsertSort(a,i,a[i]);
    }

    for (int i = 0; i < 13; ++i) {
        printf("%d ", a[i]);
    }
}

int main(int argc, char *argv[]) {
    int a[SIZE] = {23, 4, 56, 7, 8, 9, 8, 76, 5, 4, 34, 5, 6};
    
//    折半插入排序
    printf("折半插入排序:\n");
    Main_halfInsertSort(a, SIZE);
    printf("\n");

    return 0;
}

设计难点：

二分结束后正确的插入位置 right+1

向后挪

for (int i = size-1; i >= right+1; --i) {
        a[i+1] = a[i];
}

插入

a[right+1] = v;

Go实现

func halfInsertSort(a *[len(a1)]int, size int, value int) {

	left := 0
	right := size - 1
	var mid, i int

	//1.二分查找
	for left <= right {
		mid = (left + right) / 2

		if value > a[mid] {
			left = mid + 1
		} else {
			right = mid - 1
		}
	}

	//此时待插入的点为 right + 1

	//2.向后挪动
	for i = size - 1; i >= right+1; i-- {
		a[i+1] = a[i]
	}
	//2.1 插入
	a[right+1] = value
}

func Main_halfInsertSort(a *[len(a1)]int, size int){
	for i := 0; i < size; i++ {
		halfInsertSort(a,i,a[i])
	}

	// 打印
	for _, v := range a {
		fmt.Printf("%d ", v)
	}
}

func main() {
   Main_halfInsertSort(&a1, len(a1))
}

1 2 2 3 5 6 6 8 9 23 59 92 94

希尔排序

更高级的插入排序算法，同样也是优化在查找

希尔排序算法的快慢很大程度上取决于增量序列

逻辑简述：排序好每段序列

#include<stdio.h>

#define SIZE 13

int a2[SIZE] = {23, 4, 56, 7, 8, 9, 8, 76, 5, 4, 34, 5, 6};

/**
 * 希尔排序
 * @param a 数组
 * @param n 原始序列个数
 * @param h 间隔量
 */
void h_sorting(int a[], int n, int h) {
    int i, j;
    int x;

    //从第一个增量开始遍历数列，因为
    for (i = h; i < n; ++i) {
        x = a[i];//保留原数据
        for (j = i - h; (j >= 0) && (x < a[j]); j = j - h) {
            a[j+h] = a[j];
        }
        a[j+h] = x;
    }
}

void shell_sort(int a[],int size){
    int h[4] = {8,4,2,1};//希尔增量序列

    for (int i = 0; i < 4; ++i) {
        h_sorting(a,size,h[i]);
    }

    for (int i = 0; i < SIZE; ++i) {
        printf("%d ", a[i]);
    }
}

int main(){
    printf("希尔排序:\n");
    shell_sort(a2, SIZE);
    printf("\n");
}

序列增量

三种插入排序算法比较

难点

找到待插入的点
向后移动插入

交换排序

冒泡排序

逻辑简述：

依次交换将最大的元素放到最后

#include<stdio.h>
#include <stdbool.h>

#define SIZE 13

int a1[SIZE] = {23, 4, 56, 7, 8, 9, 8, 76, 5, 0, 34, 5, 6};

void bubbleSort(int a[], int size) {

    int i, j, tmp;
    bool ok;

    //循环比较
    for (i = 0; i < size; ++i) {
        //循环比较
        ok = true;//优化，因为没再发送交换，就说明遍历完了
        for (j = 0; j < size - i - 1; ++j) {//！ 防止越界
            if (a[j] > a[j + 1]) {//! 这里是前一个比后一个，不是与a[i]相比
                //交换
                tmp = a[j + 1];
                a[j + 1] = a[j];
                a[j] = tmp;

                //交换
//                a1[j] = a1[j] ^ a1[j + 1];
//                a1[j + 1] = a1[j] ^ a1[j + 1];
//                a1[j] = a1[j] ^ a1[j + 1];
                ok = false;
            }
        }

//        没在发送交换，可以推出了
        if (ok) {break;}
    }
    
	//打印数组
    for (int k = 0; k < size; ++k) {
        printf("%d ", a[k]);
    }
}

int main(int argc, char *argv[]) {//05
//    冒泡排序
    bubbleSort(a1, SIZE);
    printf("\n");

    return 0;
}

设计难点：

比较时的防止越界 j < size - i - 1;
前后比较 if (a[j] > a[j + 1])
理解排序何时结束，在一次循环中不再发生交换时就结束了 if (ok) {break;}

Go实现

快速排序

逻辑简述：

始终保持中数两边与中数是排好序的(并不是保证两边内部是排好序的，只是对比中数来说是排好的)

void quickSort(int a[], int left, int right) {

    //定义变量
    int l = left, r = right - 1;//！ 这里要注意数组越界
    int mid = a[(l + r) / 2];
    int tmp;

    //以中数两边排序
    do {
        while (a[l] < mid) ++l;//在左半部分寻找比mid中大的数
        while (a[r] > mid) --r;//在右半部分寻找比mid中小的数

//        存在左边小于中数或右边大于中数的数时
//        交换
        if (l <= r) {
            tmp = a[l];
            a[l] = a[r];
            a[r] = tmp;

//缺点，如果异或到自身会变成0，不建议使用
//            a[l] = a[l] ^ a[r];
//            a[r] = a[l] ^ a[r];
//            a[l] = a[l] ^ a[r];
        }

//        继续找
        ++l, --r;
    } while (l <= r);

    //分治
//    左边还没排完序，排位会left >= r，则递归排左半边
    if (left < r) quickSort(a, left, r);
//    右边没排完完序，排位会l >= right，则递归排右半边
    if (l < right) quickSort(a, l, right);
}

实现难点：

循环半边找数 while (a[l] < mid) ++l; while (l <= r);

分治递归思想

    //分治
//    左边还没排完序，排位会left >= r，则递归排左半边
    if (left < r) quickSort(a, left, r);
//    右边没排完完序，排位会l >= right，则递归排右半边
    if (l < right) quickSort(a, l, right);

Go实现：

总结两种交换排序算法

首先说明一点，在交换排序时不用使用异或交换。不要为了那丢丢的性能和空间区导致错误

小数组建议使用插入排序

选择排序

简单选择排序

逻辑简述：

选择最小的，然后跟它换位，保证前面的排序

#include<stdio.h>

#define SIZE 13
int a[SIZE] = {23, 4, 56, 7, 8, 9, 8, 76, 5, 4, 34, 5, 6};


void selectSort(int a[], int size) {

//    存储最小值下标 临时变量
    int min, tmp;

//    循环变量
    for (int i = 0; i < size; ++i) {
        min = i;
//        循环变量找到最小值
        for (int j = i + 1; j < size; ++j) {
            //! 这里是min,不能是i，因为设置为i时不会动态找到最小，只会找到比i小的
            if (a[min] > a[j]) {//容易逻辑出错
                min = j;
            }
        }

//        如果最小值不等于原来的值则交换
        if (i != min) {
            tmp = a[i];
            a[i] = a[min];
            a[min] = tmp;
        }
    }

//    遍历输数组
    for (int i = 0; i < size; ++i) {
        printf("%d ", a[i]);
    }
}

int main(int argc, char *argv[]) {//04

    selectSort(a, SIZE);

    return 0;
}

实现难点：

动态比对获取最小值 if (a[min] > a[j])

Go实现

算法分析

堆排序

前置知识

堆从结构上来说，是一棵完全二叉树，完全二叉树有一个这样的性质: 如果对一棵有n个结点的完全二叉树的结点,按层次从上到下,从左至右,从1开始编号，则对编号为i的结点,有:

如果i=1,则结点i是二叉树的根，无父节点。

如果i>1,则父节点为[i/2]。

如果2i >n,结点i无左孩子(结点i为叶子结点);否则其左子结点的编号是2i。

如果2i＋1 >n，则结点i无右孩子;否则其右子结点的编为2i +1。

空穴上滤算法

/**
 * 空穴上行算法
 * @param H
 * @param v
 */
void Insert_MinHeap(HeapStruct* H,ElemType v){
    int i; //指向空穴节点下标
    
//1.从空穴开始，也就是H->Size的下一位
//2.判断空穴父节点与插入元素的大小（挪动）
    //2.1 空穴父节点 >= 插入元素 => 空穴父节点值到空穴节点 => 空穴父节点变成空穴节点
//3.空穴父节点 < 插入元素 => 插入元素值插入到空穴节点中

//    1.直接从空穴开始 + 2.挪动
    for (i = ++H->Size; H->ElemTypes[i/2] > v;i = i/2) {
        //2.1 空穴父节点 >= 插入元素 => 空穴父节点值到空穴节点 => 空穴父节点变成空穴节点
        H->ElemTypes[i] = H->ElemTypes[i/2];
    }
    //3.空穴父节点 < 插入元素 => 插入元素值插入到空穴节点中
    H->ElemTypes[i] = v;
}

为什么要将H->Elements[0]填充为INT_MIN?

因为当空穴上行达到顶层(13)时，此时父节点为H->Elements[1/2]=H->Elements[0]由此会退出比较。

空穴下滤算法

ElemType Delete_Min(HeapStruct *H) {
//    保存最小值，准备出堆的
    ElemType min = H->ElemTypes[1];
//    保存最后需要移动的元素
    ElemType last = H->ElemTypes[H->Size--];

    int i;//空穴节点的下标
    int child;//指向空穴的较小孩子节点

    //i = 1 根节点
    for (i = 1; 2 * i <= H->Size; i = child) {

        //child 指向最小值
        child = 2 * i;//左子节点
        //判断右子节点
        if (child + 1 <= H->Size && (H->ElemTypes[child] > H->ElemTypes[child+1]))//存在右子节点
        {
            ++child;
        }

//        较小的子节点小于最后一个节点
        if (H->ElemTypes[child] <last){
//            空穴插入小的子节点
            H->ElemTypes[i] = H->ElemTypes[child];
        } else{
//            退出寻找子节点
            break;
        }
    }

//  插入到最后的子节点
    H->ElemTypes[i] = last;

//    返回预先保留好的最小值
    return min;
}

使用堆排序

void heap_sort(ElemType a[],int n){
    //初始化一个堆结构体
    HeapStruct *H = Init_Heap(n);

    //堆排序的步骤
    //(1) 建立堆
    for (int i = 0; i < n; ++i) {
        Insert_MinHeap(H,a[i]);
    }

    printf("one\n");
    for (int i = 0; i < n; ++i) {
        printf("%d ", H->ElemTypes[i]);
    }

    printf("\n");

    //(2) 删除最小值
    for (int i = 0; i < n; ++i) {
        a[i] = Delete_Min(H);
    }

    //(3) 释放堆
    free(H->ElemTypes);
    free(H);

}

优化空间复杂度 in-place版本

逐个下滤算法流程

从右往左，从下网上，从子节点的父节点开始

/**
 * 逐个下滤
 * @param A
 * @param i  需要下滤的编号(根节点)
 * @param n  有效元素的个数
 */
void PrecDown(ElemType A[], int i, int n) {
    int child; //指向空穴节点的较大孩子
    ElemType tmp; //保存空穴节点元素值

    //1.保存根节点也就是最大值（tmp = A[i]）
    //2.由于完全二叉树的特性，退出循环的条件为找到子节点或空穴节点小于待插入元素
    //3.子节点变成新的头节点
    for (tmp = A[i]; Lchild(i) < n; i = child) {
        //左节点
        child = Lchild(i);
        //右节点存在且大于左节点
        if (child + 1 < n && (A[child + 1] > A[child])) {
            child++;
        }
        //空穴节点大于待插入元素
        if (A[child] > tmp) {
            //替换父节点
            A[i] = A[child];
        } else {
            break;
        }
    }

    A[i] = tmp;
}

In-place排序算法逻辑

先逐个下率找到最大值，取出最大值，用子节点填充，再逐个下率找到最大值……

void heap_sort2(ElemType a[], int n) {
    int tmp;

    //建立最大堆,逐个下滤建立
    //1.从最后一个子节点的父节点开始，从右往左，从下往上
    //2.节点存在
    //3.依次插入
    for (int i = Parent(n - 1); i >= 0; i--) {
        PrecDown(a, i, n);
    }

    //调整再下滤
    for (int i = n - 1; i > 0; i--) {
        //交换第一个元素与排好序的元素
        tmp = a[i];
        a[i] = a[0];
        a[0] = tmp;
//        swap(&a[0],&a[i]);
        PrecDown(a, 0, i);
    }
}

逻辑简述：

堆的数据类型
堆的插入操作空穴上行
堆取出头元素并删除最小值操作空穴下行

完整代码

/**
    @C version: 11
    @project: AlgorithmBook
    @ide: CLion
    @file: heapSort.c
    @author: Lido
    @time: 2022-03-13 21:39
    @description:   堆排序
*/

#include<stdio.h>
#include <stdlib.h>
#include <limits.h>

typedef int ElemType;

#define SIZE 13
int a1[SIZE] = {23, 4, 56, 7, 8, 9, 8, 76, 5, 4, 34, 5, 6};

//定义堆的数据结构
typedef struct HeapStruct {
    int Cap;//容量
    int Size;//实际的节点数
    ElemType *ElemTypes; //连续的空间
} HeapStruct;

/**
 * 初始化数据结构
 * @param n
 * @return
 */
HeapStruct *Init_Heap(int n) {
//    创建结构体
    HeapStruct *hs = malloc(sizeof(*hs));
//    初始化结构体中数据
    hs->Cap = n;
    hs->Size = 0;
//     分配空间
    hs->ElemTypes = malloc(sizeof(ElemType) * (n + 1));
    hs->ElemTypes[0] = INT_MIN;
    return hs;
}

/**
 * 插入最小值
 * @param H
 * @param v
 */
void Insert_MinHeap(HeapStruct *H, ElemType v) {
    int i; //指向空穴节点下标

//    直接从空穴开始
    for (i = ++H->Size; H->ElemTypes[i / 2] > v; i = i / 2) {
        H->ElemTypes[i] = H->ElemTypes[i / 2];
    }

    H->ElemTypes[i] = v;
}

ElemType Delete_Min(HeapStruct *H) {
//    保存最小值，准备出堆的
    ElemType min = H->ElemTypes[1];
//    保存最后需要移动的元素
    ElemType last = H->ElemTypes[H->Size--];

    int i;//空穴节点的下标
    int child;//指向空穴的较小孩子节点

    //i = 1 根节点
    for (i = 1; 2 * i <= H->Size; i = child) {

        //child 指向最小值
        child = 2 * i;//左子节点
        //判断右子节点
        if (child + 1 <= H->Size && (H->ElemTypes[child] > H->ElemTypes[child+1]))//存在右子节点
        {
            ++child;
        }

//        较小的子节点小于最后一个节点
        if (H->ElemTypes[child] <last){
//            空穴插入小的子节点
            H->ElemTypes[i] = H->ElemTypes[child];
        } else{
//            退出寻找子节点
            break;
        }
    }

//  插入到最后的子节点
    H->ElemTypes[i] = last;

//    返回预先保留好的最小值
    return min;
}

void heap_sort(ElemType a[],int n){
    //初始化一个堆结构体
    HeapStruct *H = Init_Heap(n);

    //堆排序的步骤
    //(1) 建立堆
    for (int i = 0; i < n; ++i) {
        Insert_MinHeap(H,a[i]);
    }

    //(2) 删除最小值
    for (int i = 0; i < n; ++i) {
        a[i] = Delete_Min(H);
    }

    //(3) 释放堆
    free(H->ElemTypes);
    free(H);

}

int main(int argc, char *argv[]) {

    heap_sort(a1,SIZE);

    for (int i = 0; i < SIZE; ++i) {
        printf("%d ", a1[i]);
    }

    return 0;
}

优化版的完整代码

/**
    @C version: 11
    @project: AlgorithmBook
    @ide: CLion
    @file: heapSort.c
    @author: Lido
    @time: 2022-03-13 21:39
    @description:   堆排序
*/

#include<stdio.h>
#include <stdlib.h>
#include <limits.h>

typedef int ElemType;

#define SIZE 13
int a1[SIZE] = {23, 4, 56, 7, 8, 9, 8, 76, 5, 4, 34, 5, 6};

//定义堆的数据结构
typedef struct HeapStruct {
    int Cap;//容量
    int Size;//实际的节点数
    ElemType *ElemTypes; //连续的空间
} HeapStruct;

/**
 * 初始化数据结构
 * @param n
 * @return
 */
HeapStruct *Init_Heap(int n) {
//    创建结构体
    HeapStruct *hs = malloc(sizeof(*hs));
//    初始化结构体中数据
    hs->Cap = n;
    hs->Size = 0;
//     分配空间
    hs->ElemTypes = malloc(sizeof(ElemType) * (n + 1));
    hs->ElemTypes[0] = INT_MIN;
    return hs;
}

/**
 * 插入最小值
 * @param H
 * @param v
 */
void Insert_MinHeap(HeapStruct *H, ElemType v) {
    int i; //指向空穴节点下标

//    直接从空穴开始
    for (i = ++H->Size; H->ElemTypes[i / 2] > v; i = i / 2) {
        H->ElemTypes[i] = H->ElemTypes[i / 2];
    }

    H->ElemTypes[i] = v;
}

ElemType Delete_Min(HeapStruct *H) {
//    保存最小值，准备出堆的
    ElemType min = H->ElemTypes[1];
//    保存最后需要移动的元素
    ElemType last = H->ElemTypes[H->Size--];

    int i;//空穴节点的下标
    int child;//指向空穴的较小孩子节点

    //i = 1 根节点
    for (i = 1; 2 * i <= H->Size; i = child) {

        //child 指向最小值
        child = 2 * i;//左子节点
        //判断右子节点
        if (child + 1 <= H->Size && (H->ElemTypes[child] > H->ElemTypes[child + 1]))//存在右子节点
        {
            ++child;
        }

//        较小的子节点小于最后一个节点
        if (H->ElemTypes[child] < last) {
//            空穴插入小的子节点
            H->ElemTypes[i] = H->ElemTypes[child];
        } else {
//            退出寻找子节点
            break;
        }
    }

//  插入到最后的子节点
    H->ElemTypes[i] = last;

//    返回预先保留好的最小值
    return min;
}

// 完全二叉树节点
# define Parent(i) (((i)-1)/2)
# define Lchild(i) (2*(i)+1)
# define Rchild(i) (Lchild(i)+1)

/**
 * 逐个下滤
 * @param A
 * @param i  需要下滤的编号
 * @param n  有效元素的个数
 */
void PrecDown(ElemType A[], int i, int n) {
    int child; //指向空穴节点的较大孩子
    ElemType tmp; //保存空穴节点元素值

    for (tmp = A[i]; Lchild(i) < n; i = child) {
        //左节点
        child = Lchild(i);
        //右节点存在且大于左节点
        if (child + 1 < n && (A[child + 1] > A[child])) {
            child++;
        }
        if (A[child] > tmp) {
            A[i] = A[child];
        } else {
            break;
        }
    }

    A[i] = tmp;
}

void heap_sort(ElemType a[], int n) {
    //初始化一个堆结构体
    HeapStruct *H = Init_Heap(n);

    //堆排序的步骤
    //(1) 建立堆
    for (int i = 0; i < n; ++i) {
        Insert_MinHeap(H, a[i]);
    }

    printf("one\n");
    for (int i = 0; i < n; ++i) {
        printf("%d ", H->ElemTypes[i]);
    }

    printf("\n");

    //(2) 删除最小值
    for (int i = 0; i < n; ++i) {
        a[i] = Delete_Min(H);
    }

    //(3) 释放堆
    free(H->ElemTypes);
    free(H);

}

void heap_sort_In_Place(ElemType a[], int n) {
    int tmp;

    //建立最大堆,逐个下滤建立
    for (int i = Parent(n - 1); i >= 0; i--) {
        PrecDown(a, i, n);
    }

    //调整再下滤
    for (int i = n - 1; i > 0; i--) {
        tmp = a[i];
        a[i] = a[0];
        a[0] = tmp;
//        swap(&a[0],&a[i]);
        PrecDown(a, 0, i);
    }
}

int main(int argc, char *argv[]) {

//    heap_sort(a1, SIZE);

    heap_sort_In_Place(a1, SIZE);

    for (int i = 0; i < SIZE; ++i) {
        printf("%d ", a1[i]);
    }

    return 0;
}

设计难点：

堆的数据类型
堆的插入操作空穴上行
堆取出头元素并删除最小值操作空穴下行
逐行下滤
in-place算法

归并排序（外部排序）

逻辑简述：

先划分再合并

1.划分

/**
 * 划分
 * @param a
 * @param tempArr 辅助空间
 * @param left 
 * @param right
 */
void msort(int a[], int tempArr[], int left, int right) {
//    当只有一个元素，不再划分，已经有序
    if (left < right) {
//        找中间点
        int mid = (left + right) / 2;
//        递归划分左半区域
        msort(a, tempArr, left, mid);
//        递归划分右半区域
        msort(a, tempArr, mid + 1, right);
//        再合并
        merge(a, tempArr, left, mid, right);
    }
}

2.排序合并

void merge(int a[], int tempArr[], int left, int mid, int right) {
    //标记左半区第一个未排序的元素
    int l_pos = left;
    //标记右半区第一个未排序的元素
    int r_pos = mid + 1;
    //临时数组元素的下标
    int pos = left;

    //合并
    while (l_pos <= mid && r_pos <= right) {
//        左半区第一个元素更小
        if (a[l_pos] < a[r_pos])
            tempArr[pos++] = a[l_pos++];
        else
            tempArr[pos++] = a[r_pos++];
    }

    //合并左半区剩余的元素
    while (l_pos <= mid)
        tempArr[pos++] = a[l_pos++];

    //合并右半区剩余的元素
    while (r_pos <= right)
        tempArr[pos++] = a[r_pos++];

//    把临时数组覆盖原始数组
    while (left <= right) {
        a[left] = tempArr[left];
        left++;
    }
}

3.归并入口函数

/**
 * 归并排序的入口
 * @param a
 * @param n
 */
void mergeSort(int a[], int n) {
    //分配一个辅助的数组
    int *tempArr = (int *) malloc(n * sizeof(int));
    //分配内存成功
    if (tempArr) {
        //划分
        msort(a, tempArr, 0, n - 1);
        free(tempArr);
    } else {
        printf("Fail to alloc memory!");
    }
}

4.主函数

int main(int argc, char *argv[]) {
    mergeSort(a5, 13);
    for (int i = 0; i < 13; ++i) {
        printf("%d ", a5[i]);
    }
    return 0;
}

基数排序

逻辑简述：

对于一组数据，我们可以按照每一位对它们进行排序。比如，考虑下面一组十进制数。

329 457 839 355

先按最后一位从小到大排序，得到如下结果。

355 457 329 839

注意，329和839的最后一位相同，所以我们保持其相对顺序不变。

再按中间一位从小到大排序，得到如下结果。

329 839 355 457

这里也存在355和457中间一位相同的情况，仍然是保持其相对顺序不变。

最后按第一位从小到大排序，得到如下结果。

329 355 457 839

代码实现

1.求出最长的数字的长度

int maxbit(int data[], int n) //辅助函数，求数据的最大位数
{
    int maxData = data[0];      ///< 最大数
    /// 先求出最大数，再求其位数，这样有原先依次每个数判断其位数，稍微优化点。
    for (int i = 1; i < n; ++i) {
        if (maxData < data[i])
            maxData = data[i];
    }
    int d = 1;
    while (maxData >= 10) {
        maxData /= 10;
        ++d;
    }
    return d;
}

2.基数排序算法

void radixSort(int a[], int len) {

 //创建存放基数排序的空间
    int *tmp = (int *) calloc(len,sizeof(int));
    //计数器
    int *count = (int *) calloc(10,sizeof(int));
    int i, j, k;
    int i, j, k;
    //除数
    int radix = 1;
    //求出最长的数字的长度
    int d = maxbit(a, len);

    //按数字最长循环
    for (i = 1; i <= d; i++) {
        //每次分配前清空计数器
        for (j = 0; j < 10; j++)
            count[j] = 0;

        //统计每个桶中的记录数
        //[0] 1 [1] 3 [2] 3... 结尾为0的数字有1个，结尾为1的数字有3个...
        //23, 4, 56, 7, 8, 9, 8, 76, 5, 4, 34, 5, 6
        //[0] 0 [1] 0 [2] 0 [3] 1 [4] 3 [5] 2
        //[6] 3 [7] 1 [8] 2 [9] 1
        for (j = 0; j < len; j++) {
            k = (a[j] / radix) % 10;
            count[k]++;
        }

        //将tmp中的位置依次分配给每个桶,分配好了每一段的内存位置
        //[0] 0 [1] 0 [2] 0 [3] 1 [4] 3+1 [5] 2 + 4
        //[6] 3 + 6 [7] 1 + 9 [8] 2 + 10 [9] 1 + 12
        for (j = 1; j < 10; j++)
            count[j] = count[j - 1] + count[j];

        //!!!!!!!!!!!!!!将所有桶中记录依次收集到tmp中
        for (j = len - 1; j >= 0; j--) {
            //23, 4, 56, 7, 8, 9, 8, 76, 5, 4, 34, 5, 6
            //tmp[8]=6 tmp[5]=5 tmp[3]=34 tmp[2]=4 tmp[4]=5
            //tmp[7]=76 tmp[11]=8 tmp[12]=9 tmp[10]=8
            //tmp[6]=6 tmp[1]=4 tmp[0]=23

            //23 4 4 34 5 5 6 76 6 7 8 8 9
            k = (a[j] / radix) % 10;
            tmp[count[k] - 1] = a[j];
            count[k]--;
        }

        for (j = 0; j < len; j++) //将临时数组的内容复制到data中
            a[j] = tmp[j];
        radix *= 10;
    }

    free(tmp);
    free(count);
}

设计难点

//分隔好数据
for (j = 1; j < 10; j++)
	count[j] = count[j - 1] + count[j];

//按隔行放入桶中
for (j = len - 1; j >= 0; j--) {
	k = (a[j] / radix) % 10;
	tmp[count[k] - 1] = a[j];
	count[k]--;
}

计数排序

逻辑简述：

先确定数据的范围，例如0~100

再将数字作为位序号放入”桶”中

分配间隔的位置

代码实现

void counting_sort(int *ini_arr, int *sort_arr, int n) {
    int *count_arr = (int *) calloc(100, sizeof(int));
    int i, j, k, local;
    
    //按位置进入桶
    for (i = 0; i < n; i++)
        count_arr[ini_arr[i]]++;
    
    //0 0 0 0 2 2 1 1 2 1 0 0 0 0 0 0 0 0 0 
    //0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 1 0 
    //0 0 0 0 0 0 0 0 1 0 0 0

    //分配位置
    for (k = 1; k < 50; k++)
        count_arr[k] += count_arr[k - 1];
    
    //0 0 0 0 2 4 5 6 8 9 9 9 9 9 9 9 9 9 9 9 9 9 9 10 
    //10 10 10 10 10 10 10 10 10 10 11 11 12 12 12 12 
    //12 12 12 12 12 12 13 13 13 13
    
    //直接输出
    for (j = 0; j <= n; ++j) {
        local = --count_arr[ini_arr[j]];
        sort_arr[local] = ini_arr[j];
    }
    free(count_arr);

    printf("\n");
}

完整代码

/**
    @C version: 11
    @project: AlgorithmBook
    @ide: CLion
    @file: countingSort.c
    @author: Lido
    @time: 2022-03-15 15:55
    @description:   计数排序
*/

#include<stdio.h>
#include <stdlib.h>

int a[13] = {23, 4, 36, 7, 8, 9, 8, 46, 5, 4, 34, 5, 6};

void counting_sort(int *ini_arr, int *sort_arr, int n) {
    int *count_arr = (int *) calloc(100, sizeof(int));
    int i, j, k, local;
    //按位置进入桶
    for (i = 0; i < n; i++)
        count_arr[ini_arr[i]]++;

    //分配位置
    for (k = 1; k < 50; k++)
        count_arr[k] += count_arr[k - 1];
    //直接输出
    for (j = 0; j <= n; ++j) {
        local = --count_arr[ini_arr[j]];
        sort_arr[local] = ini_arr[j];
    }
    free(count_arr);
}

int main(int argc, char *argv[]) {

    int a1[13];
    counting_sort(a, a1, 13);
    for (int i = 0; i < 13; ++i) {
        printf("%d ", a1[i]);
    }

    return 0;
}

简单的内存优化

void counting_sort(int *ini_arr, int *sort_arr, int n) {
    //简单内存优化
    int max = 0;
    for (int i = 0; i < n; ++i) {
        if (max < ini_arr[i]) {
            max = ini_arr[i];
        }
    }

    int *count_arr = (int *) calloc(max+1, sizeof(int));
    int i, j, k, local;
    //按位置进入桶
    for (i = 0; i < n; i++)
        count_arr[ini_arr[i]]++;

    //分配位置
    for (k = 1; k < 50; k++)
        count_arr[k] += count_arr[k - 1];
    //直接输出
    for (j = 0; j <= n; ++j) {
        local = --count_arr[ini_arr[j]];
        sort_arr[local] = ini_arr[j];
    }
    free(count_arr);
}

设计难点：

巧妙的位置分配

 for (k = 1; k < 50; k++)
        count_arr[k] += count_arr[k - 1];

桶排序

逻辑简述：

创建一个满足数字大小的桶

将数字大小作为序号放入桶中

按序号大小输出

桶排序

void bucketSort(int a[],int len){
    //求出最大值
    int max,k=0,i;
    for (int i = 0; i < len; ++i) {
        if (max < a[i]) {
            max = a[i];
        }
    }

    //开辟空间，要大一位
    ++max;
    //创建和初始化桶
    int *tmpArr = (int *)calloc(max, sizeof(int));

    //桶排序核心代码
    //将数字作为序号放入桶中
    for (i = 0; i < len; ++i) {
        tmpArr[a[i]]++;
    }

    //输出
    for (i = 0; i < max+1; ++i) {
        while (tmpArr[i] != 0) {
            a[k++] = i;
            --tmpArr[i];
        }
    }
}

完整代码

#include<stdio.h>
#include <stdlib.h>

#define SIZE 13
int a[13] = {23, 4, 56, 7, 8, 9, 8, 76, 5, 4, 34, 5, 6};

void bucketSort(int a[],int len){
    //求出最大值
    int max,k=0,i;
    for (int i = 0; i < len; ++i) {
        if (max < a[i]) {
            max = a[i];
        }
    }

    //开辟空间，要大一位
    ++max;
    //创建和初始化桶
    int *tmpArr = (int *)calloc(max, sizeof(int));

    //桶排序核心代码
    //将数字作为序号放入桶中
    for (i = 0; i < len; ++i) {
        tmpArr[a[i]]++;
    }

    //输出
    for (i = 0; i < max+1; ++i) {
        while (tmpArr[i] != 0) {
            a[k++] = i;
            --tmpArr[i];
        }
    }
}

int main(int argc, char *argv[]) {//07
    bucketSort(a,SIZE);

    for (int i = 0; i < SIZE; ++i) {
        printf("%d ", a[i]);
    }

    return 0;
}

设计难点：

要想到最后的输出是，桶数组的序号

  for (i = 0; i < max+1; ++i) {
        while (tmpArr[i] != 0) {
            a[k++] = i;
            --tmpArr[i];
        }
    }

排序算法分析与应用

除非要排序的内容是一个复杂对象的多个数字属性，且其原本的初始顺序存在意义，那么我们需要在二次排序的基础上保持原有排序的意义，才需要使用到稳定性的算法，例如要排序的内容是一组原本按照价格高低排序的对象，如今需要按照销量高低排序，使用稳定性算法，可以使得想同销量的对象依旧保持着价格高低的排序展现，只有销量不同的才会重新排序。（当然，如果需求不需要保持初始的排序意义，那么使用稳定性算法依旧将毫无意义）。

稳定排序算法：冒泡排序、插入排序、归并排序、（计数排序、桶排序与基数排序）
不稳定排序算法：希尔排序、选择排序、堆排序与快速排序

应用场景分析：

（1）若数据规模较小（如n <= 50），可以使用简单的直接插入排序或者直接选择排序（不稳定）。（2）若文件的初始状态基本有序，排序关键字移动次数较少，则应选用直接插入或冒泡排序为宜；（3）若文件初始状态随机分布，则应选用快速排序为宜，平均时间复杂度O(nlogn)；（4）若数据规模较大，则应采用时间复杂度为O(nlogn)的排序方法：快速排序、堆排序或归并排序；

快速排序是目前基于比较的内部排序中被认为是最好的方法，当待排序的关键字是随机分布时，快速排序的平均时间最短；虽然可能退化为O(N^2)，但这种概率很小。 ps：堆排序每次取一个最大值和堆底部的数据交换，重新筛选堆，把堆顶的X调整到位，有很大可能是依旧调整到堆的底部（堆的底部X显然是比较小的数，才会在底部），然后再次和堆顶最大值交换，再调整下来，可以说堆排序做了许多无用功。堆排序过程里的交换跟快排过程里的交换虽然都是常量时间，但是常量时间差很多。

堆排序所需的辅助空间少于快速排序，并且不会出现快速排序可能出现的最坏情况。堆排序和快速排序都是不稳定的。

若要求排序稳定，则可选用归并排序（外部排序）。从单个记录起进行两两归并的排序算法并不值得提倡，通常可以将它和直接插入排序结合在一起使用。推荐：先利用直接插入排序求得较长的有序子文件，然后再两两归并之。因为直接插入排序是稳定的，所以改进后的归并排序仍是稳定的。

参考文章

硬核！C语言八大排序算法，附动图和详细代码解释！

十大常见排序算法（代码实现、复杂度分析与应用场景）

【算法】排序算法之计数排序

计数排序、基数排序和桶排序

学习视频

风马实验室

PREVIOUS第十节 Go的断言、反射和Context

NEXTgo基础练习-下