4. 排序算法

1.简单排序

1.1 冒泡排序

1.1.1 步骤+核心思想

思想：（1）执行一遍核心算法：
需要把最大的数一直挪到最后面；第一遍排序 i< n-1；交换的是arr+i+1；
（2）挪动n-1轮;(n --1 )–1

步骤：
（1）首先实现一趟冒泡

void bubble(int arr[],int n);
1

（2）再实现多趟冒泡

void bubble_sort(int arr[],int n);
1

1.1.2 参考代码

void bubble(int arr[],int n){
    for(int i=0;i<n-1;++i){
        if(arr[i] > arr[i+1]){
            swap(arr+i,arr+i+1);
        }
    }
}
void bubble_sort(int arr[],int n){
    for(int i=n;i>1;i--){
        bubble(arr,i);
    }
    // while(n>1) bubble(arr,n--);
}
1
2
3
4
5
6
7
8
9
10
11
12
13

1.1.3 时间复杂度

1.1.4 空间复杂度

随着的增长，排序不需要增加额外空间，空间复杂度为o(1)。

1.1.5 优化

尝试对已排序的数列冒泡排序

1. 2. 选择排序

1.2.1 核心思想

找出最大数字和索引，和最后的数字进行交换； /索引1–n；
仍是从前往后，把最大的往后放；.//交换次数： n-1; arr+i-1 ；–1

1.2.2 步骤

首先实现一趟,找出最大数字的下标

int find_max_index(int arr[],int n);
1

实现多趟将最大数字与最后数字交换

int selection_sort(int arr[],int n);
1

1.2.3 参考代码

int find_max_index(int arr[],int n){
    int max = arr[0];
    int max_index = 0;
    for(int i=1;i<n;++i){
        if(max < arr[i]){
            max = arr[i];
            max_index = i;
        }
    }
    return max_index;
}
void selection_sort(int arr[],int n){
    for(int i=n;i>1;--i){
        int max_index = find_max_index(arr,i);
        swap(arr+max_index,arr+i-1);// i是数组长度，最后一个元素下标要减1
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

1.2.4 时间复杂度

1.2.5 空间复杂度

随着的增长，排序不需要增加额外空间，空间复杂度为0（1）。

1.2.6 优化

同时选择最大值和最小值

1.3 插入排序

1.3.1 思想

最小的往前面放； 最后一个元素是待插入元素 逆序排；i+1
插入n-2次

1.3.2 步骤

实现向有序数列插入一个数字;

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

依次在数组中插入数字

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

1.3.3 参考代码

void insert(int arr[],int n){
    for(int i=n-2;i>=0;--i){
        if(arr[i+1]<arr[i]){
            swap(arr+i+1,arr+i);
        }
    }
}
void insertion_sort(int arr[],int n){
    for(int i=2;i<=n;++i){
        insert(arr,i);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12

1.3.4 时间复杂度

一共比较
次，即o(n^2)

1.3.5 空间复杂度

随着的增长，排序不需要增加额外空间，空间复杂度为o(1)。

1.3.6 优化

用移动代替交换

void insert(int arr[],int n){ // 最后一个元素是待插入元素
    int key=arr[n-1];
    int i=0;
    for(i=n-1;i>=1&&arr[i-1]>key;--i){
        arr[i] = arr[i-1];
    }
    arr[i] = key;
}

void insertion_sort(int arr[],int n){
    for(int i=1;i<n;++i){// 插入元素i操作
        insert(arr,i+1); // i+1表示数组长度，最后一个元素表示要插入的
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

1.4 分析

试一下下面的数据比较次数和交换次数

随机
正序
逆序

1.5 分析

使用swap()和cmp()替换排序函数中的交换和比较处理。
实现向qsort一样的排序函数。
例如：
void bubble_sort(void* arr[],int n,int size,int (cmp)(const void,const void*));

1.6 小结

排序的稳定性
在待排序的序列中，存在多个相同的关键字记录，经过排序这些记录相对位置保持不变，则这种排序称为稳定的，否则称为不稳定的。

2.复杂排序

2.1. 归并排序

2. 1.1 思想

2. 1.2 步骤

实现两个有序数组的合并

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

拆分并合并数组

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

2. 1.3 参考代码

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
2
3
4
5
6
7
8
9
10
11
12
13
14
15

2. 1.4 时间复杂度

2. 1.5 空间复杂度

2. 1.6 迭代归并排序

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);
     }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

2. 1.7 练习

剑指 Offer 51. 数组中的逆序对:
https://www.jianshu.com/go-wild?ac=2&url=https%3A%2F%2Fleetcode-cn.com%2Fproblems%2Fshu-zu-zhong-de-ni-xu-dui-lcof%2F

2. 2 快速排序

2. 2.1 思想

左游标是i哨兵,右游标是j哨兵。
右边发现比基准小的数，左边发现比基准大的数，进行交换；
到最后相遇的时候，基准进行交换；

第一次交换

第二次交换

基准交换

2. 2.2 步骤

根据基准元素重排数组

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

依次排列两个部分

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

2. 2.3 参考代码

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);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

2. 2.4 时间复杂度

2. 2.5 空间复杂度

2. 2.6 优化

交换指针法

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;
}
1
2
3
4
5
6
7
8
9
10
11
12

2.3. 希尔排序

2.3.1 算法原理

给定一个长度n的列表，选择一定的步长gap，将列表分成若干个子列表sublist。
例如：长度n=9步长gap=3分成3个子列表sublist。

对每一个子列表sublist进行插入排序。
即：arr[i],arr[i+gap];
依次减小步长gap，重复上述操作。直到gap为1。
希尔排序比插入排序的优势：
通过分组排序使元素逐渐靠近最终位置，从而减少了插入排序 时的移动次数。（先粗调再微调）

2.3.2 步骤

嵌套关系
(1)根据间距gap插入

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

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

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

(3) 划分间距gap并执行排序

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

2.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);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

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

希尔排序比插入排序更加高效，其时间复杂度和空间复杂度均优于插入排序。然而，由于希尔排序是一种不稳定的排序算法，无法保证相等元素的相对位置不变，所以在某些情况下可能不适用。

2.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);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

2.4 小结

3算法选择标准

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

4 练习

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

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

选择排序
插入排序
快速排序
冒泡排序