常用的排序算法（C语言版）

交换函数：

void swap(int arr[], int i, int j)
{
    int tmp = arr[i];
    arr[i] = arr[j];
    arr[j] = tmp;
}

一、冒泡排序 Bubble Sort

基本思想：交换排序，两两比较相邻记录的关键字，如果反序则交换，知道没有反序的记录为止。

(对相邻的元素进行两两比较，顺序相反则进行交换)

原始版：

#include <stdio.h>

void BubbleSort(int arr[], int len)
{	
    for (int i = 0; i < len; ++i)
        for (int j = len - 2; j >= i; --j)
            if (arr[j] > arr[j + 1])
                swap(arr[j], arr[j + 1]);
}

int main()
{
    int arr[] = {50, 10, 90, 30, 70, 40, 80, 60, 20};
    int len = sizeof(arr)/sizeof(arr[0]);
    
    BubbleSort(arr, len);
    
    for (int i = 0; i < len; ++i)
        printf("%d\n", arr[i]);
    
    return 0;
}

改进版：

#include <stdio.h>

void BubbleSort2(int arr[], int len)
{
    bool flag = true;
    for (int i=0; i<len && flag; ++i) {
        flag = false;
        for (int j= len-2; j>=i; --j) {
            if (arr[j] > arr[j+1]) {
                swap(arr[j], arr[j+1]);
                flag = true;
            }
        }
    }
}

int main()
{
    int arr[] = {50, 10, 90, 30, 70, 40, 80, 60, 20};
    int len = sizeof(arr)/sizeof(arr[0]);
    
    BubbleSort2(arr, len);
    
    for (int i = 0; i < len; ++i)
        printf("%d\n", arr[i]);
    return 0;
}

	比较次数	数据交换	时间复杂度
最好情况	n-1	0	O(n)
最坏情况	n(n-1)/2	n(n-1)/2	O(n^2)

二、简单选择排序 Simple Selection Sort

通过n-i次关键字之间的比较，在n-i+1个记录中选出关键字最小的记录，并和第i个记录交换之

#include <stdio.h>

void SelectionSort(int arr[], int len)
{
    int min;
    for (int i = 0; i < len; ++i) {
        min = i;
        for (int j = i + 1; j < len; ++j) {
            if (arr[min] > arr[j])
                min = j;
        }

        if (min != i)
            swap(arr[min], arr[i]);
    } 
}

int main()
{
    int arr[] = {50, 10, 90, 30, 70, 40, 80, 60, 20};
    int len = sizeof(arr)/sizeof(arr[0]);
    
    SelectionSort(arr, len);
    
    for (int i = 0; i < len; ++i)
        printf("%d\n", arr[i]);
    return 0;
}

	比较次数	数据交换	时间复杂度
最好情况	n(n-1)/2	0	O(n^2)
最坏情况	n(n-1)/2	n-1	O(n^2)

三、直接插入排序 Straight Insertion Sort

将一个记录插入到已经排序好的有序表中，从而得到一个新的、记录数增1的有序表

#include <stdio.h>

void InsertSort(int arr[], int len)
{
    int i, j, tmp;
    for (i = 1; i < len; ++i) {
        tmp = arr[i];
        for (j = i - 1; j >= 0 && arr[j] > tmp; --j)
            arr[j + 1] = arr[j];

        arr[j + 1] = tmp;
    }
}

int main()
{
    int arr[] = {50, 10, 90, 30, 70, 40, 80, 60, 20};
    int len = sizeof(arr)/sizeof(arr[0]);
    
    InsertSort(arr, len);
    
    for (int i = 0; i < len; ++i)
        printf("%d\n", arr[i]);
    return 0;
}

	比较次数	数据交换	时间复杂度
最好情况	n-1	0	O(n)
最坏情况	(n+2)(n-1)/2	(n+4)(n-1)/2	O(n^2)
平均情况	(n^2)/4	(n^2)/4	O(n^2)

四、希尔排序 Shell Sort

希尔排序实际上是一种特殊的插入排序
将相距某个“增量”的记录组成一个子序列，保证在子序列内分别进行直接插入排序后得到的结果是基本有序而不是局部有序

#include <stdio.h>

void ShellSort(int arr[], int len)
{
	int increment = len;
    int i, j, tmp;

    do {
        increment = increment/3 + 1;
        for (i = increment; i < len; ++i) {
            tmp = arr[i];
            for (j = i - increment; j >= 0 && arr[j] > tmp; j-=increment)
                arr[j + increment] = arr[j];
                
            arr[j + increment] = tmp;
        }

    } while (increment > 1);
}

int main()
{
    int arr[] = {50, 10, 90, 30, 70, 40, 80, 60, 20};
    int len = sizeof(arr)/sizeof(arr[0]);
    
    ShellSort(arr, len);
    
    for (int i = 0; i < len; ++i)
        printf("%d\n", arr[i]);
    return 0;
}

时间复杂度O(n^(3/2))

五、归并排序 Merging Sort

利用分治法的思想，稳定的排序
最好、最坏与平均时间复杂度：O(nlogn)
空间复杂度：O(n+logn)

递归方法：

#include <stdio.h>
#define MAX 100

void Merge(int src[], int des[], int low, int mid, int high)
{
    int i = low, j = mid + 1, k = low;
    
    while((i <= mid) && (j <= high)) {
        if (src[i] > src[j]) {
            des[k++] = src[j++];
        } else {
            des[k++] = src[i++];
        }
    }

    while (i <= mid) des[k++] = src[i++];
    while (j <= high) des[k++] = src[j++];
}

void MSort(int src[], int des[], int low, int high)
{
    int mid;
    int tmp[MAX];
    if (low == high) {
        des[low] = src[low];
        return;
    }

    mid = (low + high) / 2;
    MSort(src, tmp, low, mid);
    MSort(src, tmp, mid + 1, high);
    Merge(tmp, des, low, mid, high);
}

void MergeSort(int arr[], int len)
{
    MSort(arr, arr, 0, len - 1);
}

int main()
{
    int arr[] = {50, 10, 90, 30, 70, 40, 80, 60, 20};
    int len = sizeof(arr)/sizeof(arr[0]);
    
    MergeSort(arr, len);
    
    for (int i = 0; i < len; ++i)
        printf("%d\n", arr[i]);
    return 0;
}

六、堆排序 Heap Sort

堆排序是一种选择排序，整体主要由构建初始堆+交换堆顶元素和末尾元素并重建堆两部分组成。其中构建初始堆经推导复杂度为O(n)，在交换并重建堆的过程中，需交换n-1次，而重建堆的过程中，根据完全二叉树的性质，[log2(n-1),log2(n-2)…1]逐步递减，近似为nlogn。所以堆排序时间复杂度一般认为就是O(nlogn)级。

代码一

#include <stdio.h>

void heapify(int arr[] , int len, int index) //堆化，堆调整
{
    if(index >= len) return;
    
    int c1 = 2*index + 1;
    int c2 = 2*index + 2;
    int max = index;

    if(c1 < len && arr[c1] > arr[max])  max = c1;        
    if(c2 < len && arr[c2] > arr[max])  max = c2;
       
    if(max != index) {
        swap(arr, max, index);
        heapify(arr, len, max);
    }
}

void build_heap(int arr[], int len) //建立堆
{
    int last_node = len - 1;
    int first = (last_node - 1)/2;

    for(int i = first; i >= 0; --i)
        heapify(arr, len, i);
}

void HeapSort(int arr[], int len) //堆排序
{
    build_heap(arr, len);

    for(int i = len - 1; i >= 0; --i) {
        swap(arr, i, 0);
        heapify(arr, i, 0);
    }
}

int main()
{
    int arr[] = {50, 10, 90, 30, 70, 40, 80, 60, 20};
    //int arr1[] = {4, 10, 3, 5, 1, 2};
    int len = sizeof(arr)/sizeof(arr[0]);
    
    HeapSort(arr, len);
    
    for (int i = 0; i < len; ++i)
        printf("%d\n", arr[i]);
    return 0;
}

运行时间主要是消耗在初始构建堆和在重建堆时的反复筛选上。
对于每个非终端节点，最多进行两次比较和互换操作，构建堆的时间复杂度O(n)
重建堆的时间复杂度O(nlogn)
最好、最坏和平均时间复杂度：O(nlogn)
不稳定

代码二

#include <stdio.h>

void HeapAdjust(int arr[], int index, int len)
{
    int j, tmp;

    for (j = 2*index + 1; j < len; j = 2*j +1) {
        tmp = arr[index];
        if (j + 1 < len && arr[j] < arr[j + 1]) ++j;

        if (arr[index] < arr[j]) {
            arr[index] = arr[j];
            index = j;
        } 

        arr[index] = tmp;
    }
}

void HeapSort(int arr[], int len)
{
    int i;
    //首先构建初始堆，每个元素的值大于其左右子树
    for (i = len/2 - 1; i >= 0; --i)
        HeapAdjust(arr, i, len);
    
    /* 之后将堆顶元素（即最大元素）与末尾元素交换 */
    /* 排除末尾元素，让剩下的元素重新构造堆 */
    for (i = len -1; i > 0; --i) {
        swap(arr, 0, i);
        HeapAdjust(arr, 0, i);
    }
}

int main()
{
    int arr[] = {50, 10, 90, 30, 70, 40, 80, 60, 20};
    //int arr1[] = {4, 10, 3, 5, 1, 2};
    int len = sizeof(arr)/sizeof(arr[0]);
    
    HeapSort(arr, len);
    
    for (int i = 0; i < len; ++i)
        printf("%d\n", arr[i]);
    return 0;
}

七、快速牌序 Quick Sort

冒泡排序的升级，交换排序。
基本思想：通过一趟排序将待排序记录分割成独立的两部分，其中一部分记录的关键子均比另一部分记录的关键字小，则可分别对这两部分记录进行排序，以达到整个序列有序的目的。

代码一

#include <stdio.h>

int partition(int arr[], int low, int high)
{
    int key = arr[low];

    while(low < high) {
        while(low < high && arr[high] >= key) --high;            
        swap(arr[high], arr[low]);

        while(low < high && arr[low] <= key) ++low;           
        swap(arr[high], arr[low]);
    }
    return low;
}

void QSort(int arr[], int low, int high)
{
    int pivot;
    if(low < high) {
        pivot = partition(arr, low, high);
        QSort(arr, low, pivot - 1);
        QSort(arr, pivot + 1, high);
    }
}

void QuickSort(int arr[], int len)
{
    QSort(arr, 0, len - 1);
}

int main()
{
    int arr[] = {50, 10, 90, 30, 70, 40, 80, 60, 20};
    //int arr1[] = {4, 10, 3, 5, 1, 2};
    int len = sizeof(arr)/sizeof(arr[0]);
    
    QuickSort(arr, len);
    
    for (int i = 0; i < len; ++i)
        printf("%d\n", arr[i]);
    return 0;
}

改进版

#include <stdio.h>

int partition(int arr[], int low, int high)
{
    int m, key, tmp;
    // 三数取中
    m = (high - low)/2 + low;

    if(arr[low] > arr[high]) swap(arr[low], arr[high]);       
    if(arr[m]> arr[high]) swap(arr[m], arr[high]);        
    if(arr[m] > arr[low]) swap(arr[m], arr[low]);
        
    key = arr[low];
    tmp = key;
    
    while(low<high) {
        while(low<high && arr[high]>=key) --high;            
        arr[low] = arr[high];
        
        while(low<high && arr[low]<=key) ++low;            
        arr[high] = arr[low];
    }
    arr[low] = tmp;
    return low;
}

void QSort(int arr[], int low, int high)
{
    int pivot;
    if(low<high) {
        pivot = partition(arr, low, high);
        QSort(arr, low, pivot - 1);
        QSort(arr, pivot + 1, high);
    }
}

void QuickSort(int arr[], int len)
{
    QSort(arr, 0, len - 1);
}

int main()
{
    int a[] = {50, 10, 90, 50, 70, 40, 80, 60, 20};
    //int a[] = {4, 10, 3, 5, 1, 2};
    int n = sizeof(a)/sizeof(a[0]);
    QuickSort(a, n);
    for(int i=0; i<n; ++i)
        printf("%d\n",a[i]);
    return 0;
}

八、链表排序

单链表的归并排序：时间复杂度O(nlogn)，空间复杂度O(1)
利用归并排序：

#include <bits/stdc++.h>
using namespace std;

struct ListNode
{
    int val;
    ListNode* next;
    ListNode(int x):val(x),next(NULL){}
};

ListNode* MergeList(ListNode* headA, ListNode* headB)
{
    ListNode *newhead = new ListNode(0);
    ListNode *tail = newhead;

    while(headA != NULL && headB != NULL) {
        if(headA->val < headB->val)
        {
            tail->next = headA;
            tail = headA;
            headA = headA->next;
        } else {
            tail->next = headB;
            tail = headB;
            headB = headB->next;
        }
    }

    while(headA != NULL) {
        tail->next = headA;
        tail = headA;
        headA = headA->next;
    }

    while(headB != NULL) {
        tail->next = headB;
        tail = headB;
        headB = headB->next;
    }
    
    ListNode* rehead = newhead->next;
    delete newhead;
    return rehead;
}

ListNode* MsortList(ListNode* head)
{
    if(head == NULL || head->next == NULL)
        return head;

    ListNode *slow = head;
    ListNode *fast = head->next;
    
    while(fast != NULL && fast->next != NULL) { //找到中间节点，再分半
        slow = slow->next;
        fast = fast->next->next;
    }
    
    ListNode *h2 = slow->next;
    slow->next = NULL;
    ListNode *p1 = MsortList(head); //递归
    ListNode *p2 = MsortList(h2);   //递归
    return MergeList(p1, p2);
}

int main()
{
    ListNode *head = new ListNode(4);
    head->next = new ListNode(2);
    head->next->next = new ListNode(1);
    head->next->next->next = new ListNode(3);
    head->next->next->next->next = new ListNode(6);
    head->next->next->next->next->next = new ListNode(5);
    head = MsortList(head);

    while(head != NULL) {
        cout<<head->val<<endl;
        head = head->next;
    }
    return 0;
}