排序算法

三种排序[选择，归并，冒泡]

选择排序

优点：处理小数据的时候很快，时间复杂度(O^2)

选择排序就跟扑克牌一样，从牌堆里面选择一张牌插入到牌中，依次选择手中的牌，把相对较小的插入到其中

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

快速排序

时间复杂度为 O(nlogn)

void quick_sort(int q[], int l, int r)
{
    if (l >= r) return;

    int i = l - 1, j = r + 1, x = q[l + r >> 1];
    while (i < j)
    {
        do i ++ ; while (q[i] < x);
        do j -- ; while (q[j] > x);
        if (i < j) swap(q[i], q[j]);
    }
    quick_sort(q, l, j), quick_sort(q, j + 1, r);
}

归并排序

**时间复杂度 O(n log n) **

void mergeSort(int arr[], int l, int r)
{
    if (l >= r)
        return;
    int mid = (l + r) / 2;
    mergeSort(arr, l, mid);
    mergeSort(arr, mid + 1, r);
    int k = 0, i = l, j = mid + 1;
    int tmp[r - l + 1];
    while (i <= mid && j <= r)
    {
        if (arr[i] < arr[j])
            tmp[k++] = arr[i++];
        else
            tmp[k++] = arr[j++];
    }
    while (i <= mid)
        tmp[k++] = arr[i++];
    while (j <= r)
        tmp[k++] = arr[j++];

    for (i = l, j = 0; i <= r; i++, j++)
        arr[i] = tmp[j];
}

快速排序和快速排序都是分治思想