基础数据结构和算法8：高级排序算法

1. 归并排序

1.1 步骤

1. 实现两个有序数组的合并

   void merge(int arr[],int n,int mid);
   

2. 拆分并合并数组

   void merge_sort(int arr[],int n);
   

1.2 参考代码

void merge(int arr[],int n,int mid){
    int temp[n];
    memcpy(temp,arr,n*sizeof(int));
    int p = 0,q = mid,k = 0;
    while(p<mid && q<n) arr[k++] = temp[p]<=temp[q]?temp[p++]:temp[q++];
    if(p<mid) memcpy(arr+k,temp+p,(mid-p)*sizeof(int));
    if(q<n) memcpy(arr+k,temp+q,(n-q)*sizeof(int));
}
void merge_sort(int arr[],int n){
    if(n <= 1) return;
    int mid = n/2;
    merge_sort(arr,mid);
    merge_sort(arr+mid,n-mid);
    merge(arr,n,mid);
}

1.3 时间复杂度

一共拆分次，每次比较个元素，一共比较次。

1.4 空间复杂度

随着的增长，排序需要增加额外空间(临时数组和递归调用函数栈)，空间复杂度为。

1.4 迭代归并排序

void Merge(int* arr,int n,int mid){
     int res[n];
     int i=0,j=mid,k=0;
     while(i<mid && j<n){
         res[k++] = (arr[i]<arr[j])?arr[i++]:arr[j++];
     }
     if(i<mid) memcpy(res+k,arr+i,(mid-i)*sizeof(int));
     if(j<n) memcpy(res+k,arr+j,(n-j)*sizeof(int));
     memcpy(arr,res,n*sizeof(int));
}
void SubMerge(int* arr,int n,int step){
    int len = n;
    for(int i=0;i+step<n;i+=step*2){ // merge index
    Merge(arr+i,min(2*step,len),step);
    len -= 2*step;
    }
}
void MergeSort(int* arr,int n){
     for(int i=1;i<n;i*=2){
         SubMerge(arr,n,i);
     }
}

练习

剑指 Offer 51. 数组中的逆序对

---

2. 快速排序

• 左游标是i哨兵,右游标是j哨兵。
  

• 第一次交换

  
  

• 第二次交换

  
  

• 基准交换

  
  

2.1 步骤

1. 根据基准元素重排数组

   int partition(int arr[],int n);
   

2. 依次排列两个部分

   void quick_sort(int arr[],int n);
   

2.2 参考代码

int partition(int arr[],int n){
    int key = arr[0];
    int p = 0,q = n-1;
    while(p<q){
        while(p<q && arr[q]>=key) q--;
        arr[p] = arr[q];
        while(p<q && arr[p]<=key) p++;
        arr[q] = arr[p];
    }
    arr[p] = key;
    return p;
}
void quick_sort(int arr[],int n){
    if(n<=1) return;
    int pivot = partition(arr,n);
    quick_sort(arr,pivot);
    quick_sort(arr+pivot+1,n-pivot-1);
}

2.3 时间复杂度

一共拆分次，每次比较个元素，一共比较次。

2.4 空间复杂度

随着的增长，排序需要增加额外空间(递归函数栈空间)，空间复杂度为。

2.5 优化

交换指针法

int partition(int arr[],int n){
    int key = arr[0];
    int p = 0,q = n-1;
    while(p<q){
        while(p<q && arr[q]>=key) q--;
        while(p<q && arr[p]<=key) p++;
        if(p>=q) break;
        swap(arr+q,arr+p);
    }
    swap(arr,arr+q);
    return q;
}

---

3. 希尔排序

3.1 原理

1. 给定一个长度n的列表，选择一定的步长gap，将列表分成若干个子列表sublist。
   例如：长度n=9步长gap=3分成3个子列表sublist。
   
2. 对每一个子列表sublist进行插入排序。
   
3. 依次减小步长gap，重复上述操作。直到gap为1。

希尔排序比插入排序的优势：
通过分组排序使元素逐渐靠近最终位置，从而减少了插入排序 时的移动次数。（先粗调再微调）

3.2 步骤

1. 划分间距gap并执行排序

   void shell_sort(int arr[],int n);
   

2. 根据间距gap执行插入排序

   void insertion_sort(int arr[],int n,int gap);
   

3. 根据间距gap插入

   void insert(int arr[],int n,int gap);
   

3.3 参考代码

void insert(int arr[],int n,int gap){
    for(int i=n-1-gap;i>=0;i-=gap){
        if(arr[i+gap]<arr[i]){
            swap(arr+i+gap,arr+i);
        }else{
            break;
        }
    }
}
void insertion_sort(int arr[],int n,int gap){
    for(int i=gap;i<=n;++i){
        insert(arr,i,gap);
    }
}
void shell_sort(int arr[],int n){
    int gap = n;
    do{
        gap = gap/2;
        insertion_sort(arr,n,gap);
    }while(gap>1);
}

比较：插入排序与希尔排序

3.5 优化

移动代替交换

void insert(int arr[],int n,int gap){   
    int key=arr[n-1];
    int i=0;
    for(i=n-1;i>=gap&&arr[i-gap]>key;i-=gap){
        arr[i] = arr[i-gap];
    }
    arr[i] = key;
}

void insertion_sort(int arr[],int n,int gap){
    for(int i=gap;i<n;++i){// 插入元素i操作
        insert(arr,i+1,gap);
    }
}

void shell_sort(int arr[],int n){
    for(int i=n/2;i>0;i/=2){// gap序列
        insertion_sort(arr,n,i);
    }
}

4. 小结

No.	算法	Algorithm	Time Complexity	Space Complexity	Stable
1	快速排序	Quicksort			No
2	归并排序	Mergesort			Yes
3	希尔排序	Shell Sort			No

5. 算法选择标准

如何选择排序算法？(定性)

No.	准则	排序算法
1	很少的元素	插入排序
2	几乎有序的元素	插入排序
3	关注最坏的情况	堆排序
4	希望能够得到一个好的平均情况下性能	快速排序
5	元素是从一个密集集合中抽取出	桶排序
6	希望尽可能少的写代码	插入排序

6. 练习

可以保持在原有时间复杂度前提下对双向链表进行排序的算法有：（不定项）

1. 堆排序
2. 并归排序
3. 快速排序
4. 希尔排序

可以保持在原有时间复杂度前提下对单向链表进行排序的算法有：（不定项）

1. 选择排序
2. 插入排序
3. 快速排序
4. 冒泡排序