十大经典排序算法

https://www.runoob.com/w3cnote/ten-sorting-algorithm.html
排序算法：
快排：
基本思路：每次都取数组的第一个元素作为比较标准（哨兵元素），凡是大于这个哨兵元素的都放在它的右边，凡是小于这个哨兵元素的都放在它的左边；递归的进行此过程，直至排序完成。
最好：nlogn 最坏：n^2 平均：nlogn

void quicksort(struct Interval *intervals, int start, int end)
{
    int i, j;
    struct Interval temp;
    if (start > end)
    {
        return;
    }
    temp = intervals[start];
    i = start;
    j = end;
    while (i != j)
    {
        while (i < j && intervals[j] >= temp)
        {
            j--;
        }
        while (i < j && intervals[i] <= temp)
        {
            i++;
        }
        if (i < j)
        {
            struct Interval tmp = intervals[i];
            intervals[i] = intervals[j];
            intervals[j] = tmp;
        }
    }
    intervals[start] = intervals[i];
    intervals[i] = temp;
    quicksort(intervals, start, i - 1);
    quicksort(intervals, i + 1, end);
}
//严蔚敏《数据结构》标准分割函数
 Paritition1(int A[], int low, int high) {
   int pivot = A[low];
   while (low < high) {
     while (low < high && A[high] >= pivot) {
       --high;
     }
     A[low] = A[high];
     while (low < high && A[low] <= pivot) {
       ++low;
     }
     A[high] = A[low];
   }
   A[low] = pivot;
   return low;
 }

 void QuickSort(int A[], int low, int high) //快排母函数
 {
   if (low < high) {
     int pivot = Paritition1(A, low, high);
     QuickSort(A, low, pivot - 1);
     QuickSort(A, pivot + 1, high);
   }
 }
非递归算法
void QuickSortNotR(int* array,int left,int right)
{
    assert(array);
    stack<int> s;
    s.push(left);
    s.push(right);//后入的right，所以要先拿right
    while(!s.empty)//栈不为空
    {
        int right = s.top();
        s.pop();
        int left = s.top();
        s.pop();

        int index = PartSort(array,left,right);
        if((index - 1) > left)//左子序列
        {
            s.push(left);
            s.push(index - 1);
        }
        if((index + 1) < right)//右子序列
        {
            s.push(index + 1);
            s.push(right);
        }
    }
}

选择排序：
首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。

再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。

重复第二步，直到所有元素均排序完毕。

最好:n^2 最坏：n^2 平均：n^2

void selectsort(struct Interval *intervals, int intervalsSize)
{
    int k;
    for (int i = 0; i < intervalsSize-1; i++)
    {
        k=i;
        for (int j = k + 1; j < intervalsSize; j++)
        {
            if (intervals[j] < intervals[k])
            {
                k = j;

            }
        }
        if (i!=k)
        {
            struct Interval tmp = intervals[i];
            intervals[i] = intervals[k];
            intervals[k] = tmp;
        }
    }
}

插入排序：
将第一待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。
从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置。（如果待插入的元素与有序序列中的某个元素相等，则将待插入元素插入到相等元素的后面。）
最好：n 最坏：n^2 平均：n

void insertsort(struct Interval *intervals, int intervalsSize)
{
    for (int i = 1; i < intervalsSize; i++)
    {
         int key=intervals[i];
         int j=i-1;
         while((j>=0) && (key<intervals[j])){
                 intervals[j+1]=intervals[j];
                 j--;
         }
         intervals[j+1]=key;
    }
}

冒泡排序：
比较相邻的元素。如果第一个比第二个大，就交换他们两个。

对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。

针对所有的元素重复以上的步骤，除了最后一个。

持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

最好：n 最坏：n^2 平均：n^2

template<typename T> //整数或浮点数皆可使用,若要使用类(class)或结构体(struct)时必须重载大于(>)运算符
void bubble_sort(T arr[], int len) {
         int i, j;
         for (i = 0; i < len - 1; i++)
                 for (j = 0; j < len - 1 - i; j++)
                         if (arr[j] > arr[j + 1])
                                 swap(arr[j], arr[j + 1]);
}

归并排序：

1.申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列；

2.设定两个指针，最初位置分别为两个已经排序序列的起始位置；

3.比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置；

4.重复步骤 3 直到某一指针达到序列尾；

5.将另一序列剩下的所有元素直接复制到合并序列尾。

最好： nlogn 最坏： nlogn 平均：nlogn

template<typename T> // 整數或浮點數皆可使用,若要使用物件(class)時必須設定"小於"(<)的運算子功能
void merge_sort(T arr[], int len) {
     T *a = arr;
     T *b = new T[len];
     for (int seg = 1; seg < len; seg += seg) {
         for (int start = 0; start < len; start += seg + seg) {
             int low = start, mid = min(start + seg, len), high = min(start + seg + seg, len);
             int k = low;
             int start1 = low, end1 = mid;
             int start2 = mid, end2 = high;
             while (start1 < end1 && start2 < end2)
                 b[k++] = a[start1] < a[start2] ? a[start1++] : a[start2++];
             while (start1 < end1)
                 b[k++] = a[start1++];
             while (start2 < end2)
                 b[k++] = a[start2++];
         }
         T *temp = a;
         a = b;
         b = temp;
     }
     if (a != arr) {
         for (int i = 0; i < len; i++)
             b[i] = a[i];
         b = a;
     }
     delete[] b;
}

。。

void merge(vector<int>& A,int start,int mid,int end) {
    vector<int> left(A.begin()+start,A.begin()+mid+1);
    vector<int> right(A.begin() + mid+1, A.begin() + end + 1);
    left.push_back(numeric_limits<int>::max());
    right.push_back(numeric_limits<int>::max());
    int leftid = 0, rightid = 0;
    for (int i = start; i <= end;++i ) {
        if (left[leftid] < right[rightid]) {
            A[i] = left[leftid];
            ++leftid;
        }
        else {
            A[i] = right[rightid];
            ++rightid;
        }
    }
}
void merge_sort(vector<int>& A, int start, int end) {
    if (start < end) {
        int mid = (start + end) / 2;
        merge_sort(A,start,mid);
        merge_sort(A,mid+1,end);
        merge(A,start,mid,end);
    }
}

。。
希尔排序
希尔排序算是对简单插入排序的一种改进，属于一种增量式的排序算法。
时间复杂度：
图片说明
一、基本原理