排序

各大类排序总结如下

冒泡排序

冒泡排序是最简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换。

//时间复杂度： O(n^2) ，空间复杂度： O(n) 。
void bubble_sort(int arry[], int left, int right) {
    for(int i = left; i < right; i++) {
        for(int j = i; j < right; j++) {
            if(arry[j] > arry[j + 1]) {
                swap(arry[j], arry[j + 1]);
            }
        }
    }
}

选择排序

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

//时间复杂度： O(n^2) ，空间复杂度： O(n) 。
void swap(int &a, int &b) {
    int tmp = a;
    a = b;
    b = tmp;
}

void select_sort(int arry[], int left, int right) {
    for(int i = left; i < right; i++) { 
        int Min = i;
        for(int j = i + 1; j <= right; j++) {
            if(arry[Min] > arry[j]) {
                Min = j;
            }
        }
        if(Min != i) {
            swap(arry[i], arry[Min]);
        }
    }
}

快速排序

从序列中选取一个作为关键字，对序列排一次序，使得关键字左侧的数都比关键字小，右侧的都大于等于关键字（左右两侧的序列依然是无序的），然后 将左侧的序列按照同样的方法进行排序，将右侧序列也按照同样的方法排序，已达到整个序列有序。

//时间复杂度： O(nlogn) ；空间复杂度： O(n) 。
 void quick_sort(int arry[], int left, int right) {
    if(left >= right) return ;
    int i = left, j = right;
    int tmp = arry[left];
    do {
        while(arry[j] > tmp && i < j) {
            j--;
        }
        if(i < j) {
            arry[i] = arry[j];
            i++;
        }
        while(arry[i] < tmp && i < j) {
            i++;
        }
        if(i < j) {
            arry[j] = arry[i];
            j--;
        }
    } while(i != j);
    arry[i] = tmp;
    quick_sort(arry, left, i - 1);
    quick_sort(arry, i + 1, right);
}

堆排序

堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。

//时间复杂度： O(nlogn) 。
void Heap_just(int a[], int root, int heap_size) {
    if(root < heap_size) {
        int Min = root;
        int l_son = root << 1 | 1;
        int r_son = (root << 1) + 2;
        if(l_son < heap_size && a[Min] > a[l_son]) Min = l_son;
        if(r_son < heap_size && a[Min] > a[r_son]) Min = r_son;
        if(Min == root) return ;
        a[root] ^= a[Min];
        a[Min] ^= a[root];
        a[root] ^= a[Min];
        Heap_just(a, Min, heap_size);
    }
}

void build_heap(int a[], int n) {
    for(int i = n / 2; i >= 0; i--) {
        Heap_just(a, i, n);
    }
}

void Heap_sort(int a[], int n) {
    build_heap(a, n);
    for(int i = n - 1; i > 0; i--) {
        a[i] ^= a[0];
        a[0] ^= a[i];
        a[i] ^= a[0];
        Heap_just(a, 0, i);
    }
}

桶排序

桶排序 (Bucket sort)或所谓的箱排序，是一个排序算法，工作的原理是将数组分到有限数量的桶子里。每个桶子再个别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序）。桶排序是稳定的，且在大多数情况下常见排序里最快的一种,比快排还要快，缺点是非常耗空间,基本上是最耗空间的一种排序算法，而且只能在某些情形下使用。实现步骤如下（无模板）

1，设置一个定量的数组当作空桶子。
2，寻访串行，并且把项目一个一个放到对应的桶子去。
3，对每个不是空的桶子进行排序。
4，从不是空的桶子里把项目再放回原来的串行中。
(时间复杂度： O(n) )

归并排序

归并排序是一种稳定的算法，采用分治的思想，有序的子序列合并得到有序序列。

//时间复杂度： O(nlogn) 。
void arry_add(int arry[], int left, int mid, int right) {
    if(left >= right) return ;
    int i = left, j = mid + 1, k = 0;
    while(i <= mid && j <= right) {
        if(arry[i] <= arry[j]) {
            tmp[k++] = arry[i++];
        } else {
            tmp[k++] = arry[j++];
            cnt += (mid - i + 1);
        }
    }
    while(i <= mid) {
        tmp[k++] = arry[i++];
    } 
    while(j <= right) {
        tmp[k++] = arry[j++];
    }
    for(i = 0; i < k; i++) {
        arry[i + left] = tmp[i];
    }
}
void merge_sort(int arry[], int left, int right) {
    if(left >= right) return ;
    int mid = (left + right) >> 1;
    merge_sort(arry, left, mid);
    merge_sort(arry, mid + 1, right);
    arry_add(arry, left, mid, right);
}