10大排序方法，其中这里只介绍前7种（第4种C语言，其它C++语言）

排序方法有十种，分别是：一、冒泡排序；二、选择排序；三、插入排序；四、希尔排序；五、归并排序；六、快速排序；七、堆排序；八、计数排序；九、桶排序；十、基数排序。

一、冒泡排序

冒泡排序是排序算法中较为简单的一种，英文称为Bubble Sort。它遍历所有的数据，每次对相邻元素进行两两比较，如果顺序和预先规定的顺序不一致，则进行位置交换；这样一次遍历会将最大或最小的数据上浮到顶端，之后再重复同样的操作，直到所有的数据有序。

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

二、选择排序

选择排序简单直观，英文称为Selection Sort，先在数据中找出最大或最小的元素，放到序列的起始；然后再从余下的数据中继续寻找最大或最小的元素，依次放到排序序列中，直到所有数据样本排序完成。

void selectionSort(int arr[], int n) {
    for (int i = 0; i < n; i++) {
        int min_idx = i;
        for (int j = i; j < n; j++)
            if (arr[j] < arr[min_idx])
                min_idx = j;
        swap(arr[min_idx], arr[i]);
    }
}

三、插入排序

插入排序英文称为Insertion Sort，它通过构建有序序列，对于未排序的数据序列，在已排序序列中从后向前扫描，找到相应的位置并插入，类似打扑克牌时的码牌。插入排序有一种优化的算法，可以进行拆半插入。

基本思路是先将待排序序列的第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列；然后从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置，直到所有数据都完成排序；如果待插入的元素与有序序列中的某个元素相等，则将待插入元素插入到相等元素的后面。

void insertionSort(int arr[], int n) {
    for (int i = 1; i < n; i++) {
        int key = arr[i];
        int j = i - 1;
 
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j = j - 1;
        }
        arr[j + 1] = key;
    }
}

四、希尔排序

希尔排序也称递减增量排序，是插入排序的一种改进版本，英文称为Shell Sort，效率虽高，但它是一种不稳定的排序算法。

插入排序在对几乎已经排好序的数据操作时，效果是非常好的；但是插入排序每次只能移动一位数据，因此插入排序效率比较低。

希尔排序在插入排序的基础上进行了改进，它的基本思路是先将整个数据序列分割成若干子序列分别进行直接插入排序，待整个序列中的记录基本有序时，再对全部数据进行依次直接插入排序。

void shell_sort(int* a,int len){
    int  i,j;
    int gap=0;
    int temp=0,k;
    for(int gap=len/2;gap>0;gap/=2){
        for(i=0;i<gap;i++){
            for(j=i+gap;j<len;i+=gap){
                temp=a[j];
                k=j-gap;
                while(k>=0&&a[k]>temp){
                    a[k+gap]=a[k];
                    k-=gap;
                }
                a[k+gap]=temp;
            }
        }
    }
}

五、归并排序

归并排序英文称为Merge Sort，归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。它首先将数据样本拆分为两个子数据样本, 并分别对它们排序, 最后再将两个子数据样本合并在一起; 拆分后的两个子数据样本序列, 再继续递归的拆分为更小的子数据样本序列, 再分别进行排序, 直到最后数据序列为1，而不再拆分，此时即完成对数据样本的最终排序。

归并排序严格遵循从左到右或从右到左的顺序合并子数据序列, 它不会改变相同数据之间的相对顺序, 因此归并排序是一种稳定的排序算法.

作为一种典型的分而治之思想的算法应用，归并排序的实现分为两种方法：

1、自上而下的递归；

2、自下而上的迭代；

void merge(int arr[], int l, int m, int r) {
    int i, j, k;
    int n1 = m - l;
    int n2 = r - m;
    int L[n1], R[n2];
 
    for (i = 0; i < n1; i++)
        L[i] = arr[l + i];
    for (j = 0; j < n2; j++)
        R[j] = arr[m + j];
 
    i = 0;
    j = 0;
    k = l;
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k] = L[i];
            i++;
        }
        else {
            arr[k] = R[j];
            j++;
        }
        k++;
    }
 
    while (i < n1) {
        arr[k] = L[i];
        i++;
        k++;
    }
 
    while (j < n2) {
        arr[k] = R[j];
        j++;
        k++;
    }
}
 
void mergeSort(int arr[], int l, int r) {
    if (l < r) {
        int m = l + (r - l) / 2;
 
        mergeSort(arr, l, m);
        mergeSort(arr, m + 1, r);
 
        merge(arr, l, m + 1, r);
    }
}

六、快速排序

快速排序,英文称为Quicksort，又称划分交换排序 partition-exchange sort 简称快排。

快速排序使用分治法（Divide and conquer）策略来把一个序列（list）分为两个子序列（sub-lists）。首先从数列中挑出一个元素，并将这个元素称为「基准」，英文pivot。重新排序数列，所有比基准值小的元素摆放在基准前面，所有比基准值大的元素摆在基准后面（相同的数可以到任何一边）。在这个分区结束之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。之后，在子序列中继续重复这个方法，直到最后整个数据序列排序完成。

int partition(int arr[], int low, int high) {
    int pivot = arr[high];
    int i = (low - 1);
 
    for (int j = low; j <= high - 1; j++) {
        if (arr[j] < pivot) {
            i++;
            swap(arr[i], arr[j]);
        }
    }
    swap(arr[i + 1], arr[high]);
    return (i + 1);
}
 
void quickSort(int arr[], int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);
 
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

七、堆排序

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

1、大顶堆：每个节点的值都大于或等于其子节点的值，在堆排序算法中用于升序排列；

2、小顶堆：每个节点的值都小于或等于其子节点的值，在堆排序算法中用于降序排列；

void heapify(int arr[], int n, int i) {
    int largest = i;
    int l = 2 * i +