目录

一、排序分类

二、插入排序 —— 只能顺序结构

1、直接插入排序 —— 稳定

2、折半插入排序 —— 稳定

3、希尔排序 —— 不稳定

三、交换排序 

1、冒泡排序 —— 稳定 —— 可链式

2、快速排序 —— 不稳定 —— 顺序

四、选择排序

1、简单选择排序 —— 不稳定 —— 可链式

2、堆排序 —— 不稳定 —— 顺序

 五、归并排序 —— 稳定

一、排序分类

二、插入排序 —— 只能顺序结构

1、直接插入排序 —— 稳定

时间复杂度：平均O(n^2)，最好O(n)， 最坏O(n^2)
空间复杂度：O(1)，因为只需要一个记录的辅助空间 r[0]

默认第一个元素有序，从第二个元素开始，把该元素存入监视哨，把该元素前的所有元素排好序列

void InsertSort(int A[],int n)
{
    int i,j;

    for(i=2;i A[0] ; j--)
                A[j+1] = A[j];   //比哨兵大的元素后移

            A[j+1] = A[0]; //将哨兵的值插入正确位置
        }
}

2、折半插入排序 —— 稳定

时间复杂度：O(n2)

空间复杂度：仍是只需要一个记录的辅助空间r[0]，所以时间复杂度为O(1)

在将一个新元素插入已排好序的数组的过程中，寻找插入点时，将待插入区域的首元素设置为a[low]，末元素设置为a[high]。

将待插入元素与a[mid]相比较，如果比参考元素小，则选择左区间，否则选择右区间，如此直至low<=high不成立，即将high+1位置及之后所有元素后移一位，并将新元素插入a[high+1]。

void BInsertSort(int a[],int n)
{
    int i,j,low,high,mid;

    for(i=2 ;i 
 
3、希尔排序 —— 不稳定 
 
 
时间复杂度：O(n(log2n)2)
 
 
空间复杂度：也是只需要一个辅助空间 r[0] ，所以时间复杂度为O(1)
 
 
 
三、交换排序  
1、冒泡排序 —— 稳定 —— 可链式 
 
 
时间复杂度：O(n2)，但若是一开始就是有序的，则时间复杂度为O(n)
 
 
 
 
void BubbleSort(int a[],int n)
{
    for(int i=0;ia[j+1]) //升序
            {
                int t=a[j];
                a[j]=a[j+1];
                a[j+1]=t;
                flag=1;
            }
        if(!flag) break; //如果某趟没有交换位置 说明已经排好序 直接跳出大循环
    }
}
 
 
 
2、快速排序 —— 不稳定 —— 顺序 
 
 
时间复杂度：O(nlog2n)
 
 
空间复杂度：最好O(log2n)，最坏O(n)
 
 
 
void quick_sort(int q[], int l, int r)
{
    if(l>=r) return 0;
 
    int x = q[l], i = l-1, j = r+1;
 
    while(i x);  //如果满足≥x 则指针左移
 
        if(i 
 
 
四、选择排序 
1、简单选择排序 —— 不稳定 —— 可链式 
 
 
时间复杂度：O(n2)
 
 
空间复杂度：O(1) 
 
 
 
void SelectSort(int a[],int n)
{
    for(int i=1;i<=n;i++)
    {
        int min=i;
        for(int j=i+1;i<=n;j++)
            if(a[j]
 
 
 
2、堆排序 —— 不稳定 —— 顺序 
 
 
时间复杂度：O(nlog2n)
 
 
空间复杂度：O(1)
 
 
堆是具有以下性质的完全二叉树：
 
①每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆。
 
②每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆。 
 
 
 
 
将无需序列构建成一个堆，根据升序降序需求选择大顶堆或小顶堆;
将堆顶元素与末尾元素交换，将最大元素"沉"到数组末端;
重新调整结构，使其满足堆定义，然后继续交换堆顶元素与当前末尾元素，反复执行调整+交换步骤，直到整个序列有序。
 
eg：
 
 调整成为大顶堆的过程略
 
 
将堆顶元素9和末尾元素4进行交换，并且将9标记为已排序状态
 
 
重新调整结构，使其继续满足堆定义
 
 
再将堆顶元素8与末尾元素5进行交换，得到第二大元素8，并将8也标记为已标记状态
 
 
继续进行调整，交换，如此反复进行，最终使得整个序列有序
 
 
 
 五、归并排序 —— 稳定 
 
 
时间复杂度：O(nlogn)
 
 
void merge_sort(int q[],int l,int r)
{
    if(l>=r) return;
 
    int mid = (l+r)/2;
 
    //递归排序左右区间
    merge_sort(q,l,mid);
    merge_sort(q,mid+1,r);

    //双指针归并左右有序区间
    int k=0,i=l,j=mid+1;
    while(i<=mid && j<=r)
        if(q[i]<=q[j]) temp[k++]=q[i++];
        else temp[k++]=q[j++];

    //如果左右区间有剩下的，补在末尾
    while(i<=mid) temp[k++]=q[i++];
    while(j<=r) temp[k++]=q[j++];
 
    //把归并好的序列复制给q[]
    for(int i=l,j=0;i<=r;i++,j++) q[i] = temp[j];
}