排序

排序算法比较

排序算法比较

一、冒泡排序（Bubble Sort）

基本思想

冒泡排序是一种简单的排序算法。它重复地走访要排序的序列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。走访序列的工作是重复地进行直到没有元素再需要交换，也就是说该序列已经排序完成。这个算法的名字由来是因为每趟比较会将当前序列未排序部分的最大的元素"沉"到序列末端，而小的元素会经由交换慢慢"浮"到序列的顶端。

代码实现

#include<stdio.h>
#define SIZE 8

void bubble_sort(int a[], int n) { //按照"从小到大"的顺序进行排列
    for(int i=0; i<n-1; i++) { //总共n个数字，要进行n-1轮循环
        bool isSwap = false; //设置标志位，优化循环次数
        for(int j=0; j<n-1-i; j++) { //每一轮循环都从第一个数字开始，到最后一个未确定的数字的前一个数字结束
            if(a[j] > a[j+1]) {//前面的比后面的大则两者进行交换
                int temp = a[j];
                a[j] = a[j+1];
                a[j+1] = temp;
                isSwap = true; //标志位置为true
            }
        }
        if(!isSwap) { //标志位为false，说明这一轮循环没有进行交换操作，直接退出循环
            return;
        }
    }
}

int main() {
    int number[SIZE] = {95, 45, 15, 78, 84, 51, 24, 12};
    bubble_sort(number, SIZE);
    for(int i=0; i<SIZE; i++) {
        printf("%d ", number[i]);
    }
    printf("\n");
    return 0;
}

二、选择排序（Selection Sort）

基本思想

选择排序是一种简单的排序算法。它首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

代码实现

#include<stdio.h>
#define SIZE 8

void select_sort(int a[], int n) { //按照"从小到大"的顺序进行排列
    for(int i=0; i<n-1; i++) { //总共n个数字，要进行n-1轮循环
        int minIndex = i; //每一轮循环都设置该轮数字为默认的最小值
        for(int j=i+1; j<n; j++) { //每一轮循环都从该轮数字的下一个数字开始，到最后一个数字结束
            if(a[minIndex] > a[j]) { //最小值比后面的大则将后面的设置为最小值
                minIndex = j;
            }
        }
        
        if(minIndex != i) {//如果这一轮循环最终的最小值不是一开始设置的默认的最小值，则两者进行交换
            int temp = a[minIndex];
            a[minIndex] = a[i];
            a[i] = temp;
        }
    }
}

int main() {
    int number[SIZE] = {95, 45, 15, 78, 84, 51, 24, 12};
    select_sort(number, SIZE);
    for(int i = 0; i < SIZE; i++) {
        printf("%d ", number[i]);
    }
    printf("\n");
    return 0;
}

三、直接插入排序（Insertion Sort）

基本思想

直接插入排序是一种简单的排序算法。它通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

代码实现

#include<stdio.h>
#define SIZE 8

void insertion_Sort(int array[], int n) { //按照"从小到大"的顺序进行排列
    for(int i=1; i<n; i++) { 
        int current = array[i]; //保存当前值
        int preIndex = i - 1; //对位置 i 来说，上一个位置为 i - 1
        while (preIndex >= 0 && current < array[preIndex]) { //如果上一个位置大于等于 0 并且 上一个位置的值大于当前值 
                array[preIndex + 1] = array[preIndex]; //对位置 preIndex 来说，下一个位置为 preIndex + 1 
                preIndex--; //对位置 preIndex 来说，上一个位置为 preIndex - 1 
        }
        array[preIndex + 1] = current; //对位置 preIndex 来说，下一个位置为 preIndex + 1 
    }
}

int main() {
    int array[SIZE] = {95, 45, 15, 78, 84, 51, 24, 12};
    insertion_Sort(array, SIZE);
    for (int i=0; i<SIZE; i++) {
        printf("%d ", array[i]);
    }
    printf("\n");
    return 0;
}

四、希尔排序（Shell Sort）

基本思想

希尔排序又叫缩小增量排序。它先将整个待排元素序列分割成gap个增量为gap的子序列（每个子序列由位置相差为gap的元素组成，整个序列正好分割成gap个子序列，每个序列中有n/gap个元素）分别进行直接插入排序，然后缩减增量为之前的一半再进行排序，待gap==1时，希尔排序就变成了直接插入排序。因为此时序列已经基本有序，直接插入排序在元素基本有序的情况下（接近最好情况），效率是很高的。gap初始值一般取len/2。

代码实现

#include <stdio.h>

void shell_sort(int array[], int n) { //按从小到大的顺序进行排列 
    int gap = n/2; //gap 表示增量，初始化为数组长度的一半 
    while(gap > 0) { //如果增量大于 0 
        for(int i=gap; i<n; i++) {
            int current = array[i]; //保存当前值 
            int preIndex = i - gap; //对位置 i 来说，上一个位置为 i - gap 
            while(preIndex >= 0 && array[preIndex] > current) { //如果上一个位置大于等于 0 并且 上一个位置的值大于当前值 
                array[preIndex + gap] = array[preIndex]; //对位置 preIndex 来说，下一个位置为 preIndex + gap 
                preIndex -= gap; //对位置 preIndex 来说，上一个位置为 preIndex - gap 
            }
            array[preIndex + gap] = current; //对位置 preIndex 来说，下一个位置为 preIndex + gap 
        }
        gap /= 2; //增量减半 
    }
}

int main() {
    int array[] = {30, 21, 17, 19, 25, 29, 14, 25};
    shell_sort(array, 8);
    printf("after sort:\n");
    for(int i=0; i<8; i++) {
        printf("%d ", array[i]);
    }
    printf("\n");
    return 0;
}

五、归并排序（Merge Sort）

基本思想

归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列。即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。

代码实现

#include <stdio.h>
#define SIZE 8

void merge(int data[], int start1, int end1, int start2, int end2) { //对左右两个分别排好序的序列进行合并 
    int result[SIZE];
    int resultIndex = 0;
    int i = start1, j = start2;
    while(i <= end1 && j <= end2) {
        if(data[i] <= data[j]) {
            result[resultIndex++] = data[i++];
        } else {
            result[resultIndex++] = data[j++];
        }
    }
    while(i <= end1) {
        result[resultIndex++] = data[i++];
    }
    while(j <= end2) {
        result[resultIndex++] = data[j++];
    }
    for(int k=start1; k<=end2; k++) {
        data[k] = result[k-start1];
    }
}

void merge_sort(int data[], int start, int end) { //按从小到大的顺序进行排列 
    int len = end - start + 1;
    if(len < 2) { //递归结束条件为序列长度小于 2 ，即序列不能再分为两个子序列
        return;
    }
    int mid = (start + end) / 2; //取中间位置 
    merge_sort(data, start, mid); //使用递归对左边序列进行归并排序 
    merge_sort(data, mid+1, end); //使用递归对右边序列进行归并排序 
    merge(data, start, mid, mid+1, end); //对左右两个分别排好序的序列进行合并 
}

void main() {
    int data[] = {30, 21, 17, 19, 25, 29, 14, 25};
    merge_sort(data, 0, SIZE-1);
    printf("after sort:\n");
    for(int i=0; i<SIZE; i++) {
        printf("%d ", data[i]);
    }
    printf("\n");
}

六、快速排序（Quick Sort）

基本思想

通过一趟排序将待排序列分隔成两个独立的子序列，其中一个子序列的关键字均比另一个子序列的关键字小，则可分别对这两个子序列继续进行排序，以达到整个序列有序。

分区方法

代码实现

#include<stdio.h>
#define SIZE 8

void swap(int data[], int i, int j) { //交换 
    if(i == j) {
        return;
    }
    int temp = data[i];
    data[i] = data[j];
    data[j] = temp;
}

int partition(int data[], int left, int right) { //分区 
    int start = left;
    int end = right;
    int key = right;
    while(start < end) {
        while(start < end && data[start] <= data[key]) { //start位置找大 
            start++;
        } 
        while(start < end && data[end] >= data[key]) { //end位置找小 
            end--; 
        } 
        swap(data, start, end); //交换start位置与end位置的值 
    } 
    swap(data, start, key); //交换start位置与key位置的值 
    return start; //返回start位置，即分区中间位置 
}

void quick_sort(int data[], int left, int right) { //按从小到大的顺序进行排列 
    if(left < right) { //递归结束条件为 left >= right 
        int pos = partition(data, left, right); //对序列进行分区 
        quick_sort(data, left, pos-1); //使用递归对左序列进行快速排序 
        quick_sort(data, pos+1, right); //使用递归对右序列进行快速排序 
    }
}

void main() {
    int data[] = {30, 21, 17, 19, 25, 29, 14, 25};
    quick_sort(data, 0, SIZE-1);
    printf("after sort:\n");
    for(int i=0; i<SIZE; i++) {
        printf("%d ", data[i]);
    }
    printf("\n");
}

七、堆排序（Heap Sort）

基本思想

堆排序是一种树形选择排序方法，它利用了堆这种数据结构。在排序的过程中，将array[0，...，n-1]看成是一颗完全二叉树的顺序存储结构，利用完全二叉树中双亲结点和孩子结点之间的关系，在当前无序区中选择关键字最大（最小）的元素。

代码实现

#include<stdio.h> 
#define SIZE 8

int data[SIZE];
int dataIndex = 0;

void swap(int parent, int pos) {
    int temp;
    temp = data[parent];
    data[parent] = data[pos];
    data[pos] = temp;
}

void fix_up() {
    int pos = dataIndex - 1;
    int value = data[pos];
    int parent = (pos - 1) / 2;

    while (parent >= 0 && value < data[parent]) {  //当前结点有父母且值小于父母
        swap(parent, pos);
        pos = parent;
        parent = (pos - 1) / 2;
        value = data[pos];
    }
}

void heap_insert(int val)
{
    data[dataIndex++] = val; //1.放到尾部
    fix_up(); //2.小根堆，向上调整
}

void fix_down(){
    if (dataIndex <= 0) {
        return;
    }
    
    int pos = 0;
    int value = data[pos];
    int left = pos * 2 + 1;
    int right = left + 1;

    while (left < dataIndex) { //左边的结点无越界 
        int refValue;
        int refPos;
        if (right < dataIndex) { //右边的结点无越界 
            refValue = data[left] < data[right] ? data[left] : data[right]; //获取子结点中较小的值 
            refPos = data[left] < data[right] ? left : right; //获取子结点中较小的值的位置 
        } else { //右边的结点有越界 
            refValue = data[left];
            refPos = left;
        }
        if (value > refValue) {
            swap(pos, refPos);
        } else {
            break;
        }
        
        pos = refPos;
        left = pos * 2 + 1;
        right = left + 1; 
        value = data[pos];
    }
}

int heap_pop() {
    if(dataIndex <= 0) {
        return -1;
    }
    int result = data[0];
    data[0] = data[dataIndex - 1]; //1.把尾部的值放到头部
    dataIndex--;
    fix_down(); //2.小根堆，向下调整
    return result;
}

void heap_sort(int arr[], int result[], int n) {
    for(int i=0; i<n; i++) {
        heap_insert(arr[i]);
    }
    for(int i=0; i<n; i++) {
        result[i] = heap_pop();
    }
}

void main() {
    int data[] = {30, 21, 17, 19, 25, 29, 14, 25};
    int result[SIZE];
    heap_sort(data, result, SIZE);
    printf("after sort:\n");
    for(int i=0; i<8; i++) {
        printf("%d ", result[i]);
    }
    printf("\n");
}

八、计数排序（Counting Sort）

基本思想

计数排序不是基于比较的排序算法，其核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。

代码实现

#include<stdio.h>
#define MAX 100
#define SIZE 8

void counting_sort(int data[], int n) { //按从小到大的顺序进行排列 
    if(n <= 1) {
        return;
    }
    
    int max = data[0];
    int min = data[0];
    for(int i=1; i<n; i++) { //求最大值与最小值 
        if(max < data[i]) {
            max = i;
        }
        if(min > data[i]) {
            min = i;
        }
    }
    
    int bucketLen = max - min + 1; //差值计数数组实际长度 
    int bucket[MAX]; //差值计数数组 
    for(int i=0; i<bucketLen; i++) { //初始化为 0，即计数从 0 开始 
        bucket[i] = 0; 
    }
    
    for(int i=0; i<n; i++) { //遍历原始数组进行计数 
        bucket[data[i] - min]++;
    }
    
    int bucketIndex = 0; //差值计数数组下标 
    int arrayIndex = 0; //原始数组下标 
    while(arrayIndex < n) { //循环条件为 arrayIndex 小于 n 
        if(bucket[bucketIndex] != 0) { //如果差值计数数组中bucketIndex位置的数量不为 0 
            data[arrayIndex] = bucketIndex + min; //通过下标（即差值）与最小值，还原数值并插入原始数组 
            bucket[bucketIndex]--; //差值计数数组中bucketIndex位置的数量减 1 
            arrayIndex++; //原始数组arrayIndex加 1 
        } else { //如果差值计数数组中bucketIndex位置的数量为 0 
            bucketIndex++; //bucketIndex加 1 
        }
    }
}

void main() {
    int data[] = {30, 21, 17, 19, 25, 29, 14, 25};
    counting_sort(data, SIZE);
    printf("after sort:\n");
    for(int i=0; i<SIZE; i++) {
        printf("%d ", data[i]);
    }
    printf("\n");
}

九、桶排序（Bucket Sort）

基本思想

桶排序与计数排序很相似，不过现在的桶不单计数，是实实在在地放入元素。按照映射函数将数据分配到不同的桶里，每个桶内元素再分别排序（可能使用别的排序算法），最后拼接各个桶中排好序的数据。映射函数人为设计，但要保证桶i中的数均小于桶j（i < j）中的数，即必须桶间必须有序，桶内可以无序。可以考虑按照数的区间范围划分桶，例如：(i - min) / arr.length。

代码实现

#include<stdio.h>
#include<malloc.h>
#define MAX 100
#define SIZE 10

struct Node { //桶结点 
    int value;
    Node *next;
};

void insertion_sort(int data[], int n) { //直接插入排序，按照"从小到大"的顺序进行排列
    for(int i=1; i<n; i++) { 
        int current = data[i]; //保存当前值
        int preIndex = i - 1; //对位置 i 来说，上一个位置为 i - 1
        while (preIndex >= 0 && current < data[preIndex]) { //如果上一个位置大于等于 0 并且 上一个位置的值大于当前值 
                data[preIndex + 1] = data[preIndex]; //对位置 preIndex 来说，下一个位置为 preIndex + 1 
                preIndex--; //对位置 preIndex 来说，上一个位置为 preIndex - 1 
        }
        data[preIndex + 1] = current; //对位置 preIndex 来说，下一个位置为 preIndex + 1 
    }
}

void bucket_sort(int data[], int n) { //按从小到大的顺序进行排序 
    int max = data[0];
    int min = data[0];
    for(int i = 1; i < n; i++){ //求最大值与最小值 
        if(data[i] > max) {
            max = data[i];
        }
        if(data[i] < min) {
            min = data[i];
        }
    }
    
    int bucketNum = (max - min) / n + 1; //计算桶的数量 
    Node bucket[MAX]; //使用结构体数组定义桶 
    for(int i=0; i<bucketNum; i++) {
        bucket[i].value = 0;
        bucket[i].next = NULL;
    }
    
    for(int i=0; i<n; i++) { //将每个元素放入桶
        int num = (data[i] - min) / n; //计算该元素属于哪个桶 
        Node *node = (Node *)malloc(sizeof(Node));
        node->value = data[i];
        node->next = bucket[num].next;
        bucket[num].next = node;
    }
    
    int arrayIndex = 0;
    for(int i=0; i<bucketNum; i++) { //遍历每个桶 
        int temp[SIZE];
        int tempIndex = 0;
        Node *p = bucket[i].next;
        Node *q;
        bucket[i].next = NULL;
        while(p != NULL) {
            temp[tempIndex++] = p->value;
            q = p;
            p = p->next;
            free(q);
        }
        insertion_sort(temp, tempIndex); //对每个桶进行直接插入排序 
        
        for(int j=0; j<tempIndex; j++) { //将排序后的数组元素存入原始数组 
            data[arrayIndex++] = temp[j];
        }
    } 
}

void main() {
    int data[] = {23, 45, 65, 21, 9, 18, 34, 43, 101, 1};
    bucket_sort(data, SIZE);
    printf("after sort:\n");
    for(int i=0; i<SIZE; i++) {
        printf("%d ", data[i]);
    }
    printf("\n");
}

十、基数排序（Radix Sort）

基本思想

基数排序先按照低位排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。

代码实现

#include<stdio.h>
#include<malloc.h>
#define SIZE 10

struct Node { //基数结点
    int value;
    Node *next;
};

void radix_sort(int data[], int n) { //按从小到大的顺序进行排序
    if(n <= 1) {
        return;
    }
   
    int max = data[0];
    for(int i=1; i<n; i++) { //求最大值
        if(max < data[i]) {
            max = data[i];
        }
    }
    int maxDigit = 0;
    while(max != 0) { //求最大值的位数
        max /= 10;
        maxDigit++;
    }
    
    Node bucket[10]; //定义结构体数组，大小为 10，因为对于 个位/十位/百位/... 来说，数值范围都是 0 ~ 9
    for(int i=0; i<10; i++) {
        bucket[i].value = 0;
        bucket[i].next = NULL;
    }
    
    int div = 1;
    for(int i=0; i<maxDigit; i++, div *= 10) { //总共需要进行maxDigit轮循环，即对于每一个位都需要进行一轮循环，先从低位开始
        for(int j=0; j<n; j++) { //对于每一轮循环，都需要遍历原始数组，通过相应位对数值进行排序
            int bucketNum = (data[j] / div) % 10; //求相应位对应的值，范围为 0 ~ 9
            Node *node = (Node *)malloc(sizeof(Node));
            node->value = data[j];
            node->next = bucket[bucketNum].next;
            bucket[bucketNum].next = node; //插入到链表头位置的下一个结点
            bucket[bucketNum].value++; //添加到该位置的结点个数加 1
        }
        
        int curCount = 0;
        for (int j=0; j<10; j++) { //遍历结构体数组，整合排序结果到原始数组中
            int nodeCount = bucket[j].value; //获取添加到该位置的结点个数
            if(nodeCount == 0) { //如果添加到该位置的结点个数为 0，则结束本次循环
                continue;
            }
            Node *p = bucket[j].next; //获取链表头位置的下一个结点
            Node *q;
            bucket[j].next = NULL;
            bucket[j].value = 0;

            curCount += nodeCount; //计算当前处理的结点总数
            int dataIndex = curCount - 1; //计算数值要插入到原始数组的位置，因为在链表中是倒着插入，所以在原始数组中也要倒着插入
            while(p != NULL) {
                data[dataIndex--] = p->value;
                q = p;
                p = p->next;
                free(q);
            }        
        }
        
        printf("loop %d: \n", i);
        for(int j=0; j<n; j++) {
            printf("%d ", data[j]);
        }
        printf("\n");
   }
}

void main() {
    int data[] = {23, 145, 5, 21, 9999, 168, 34, 493, 101, 1};
    radix_sort(data, SIZE);
    printf("after sort:\n");
    for(int i=0; i<SIZE; i++) {
        printf("%d ", data[i]);
    }
    printf("\n");
}