算法

排序算法

Posted by Liao on 2020-03-31

一、冒泡排序（稳定 O(N)～ O(N^2^)）

基本思想：两两数字比较，比较在每一趟遍历中，看当前数字会不会比下一个大，如果比下一个大则交换。每一趟交换中能找到最大的数，放在末尾。

最好情况：顺序 只需遍历一遍 T = O(N)

最坏情况：逆序 全部都得排序　T = O(N^2^)

如数组：５，３，７，１０，６，１８，４

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
第一趟：能把最大值放到最后

【３，５】，７，６，１０，４，１８　

３，【５，７】，１０，６，１８，４　

３，５，【７，１０】，６，１８，４　

３，５，７，【６，１０】，１８，４　

３，５，７，６，【１０，１８】，４　

３，５，７，６，１０，【４，１８】

第二趟：

【３，５】，７，６，１０，４

３，【５，７】，６，１０，４

３，５，【６，７】，１０，４

３，５，６，【７，１０】，４

３，５，６，７，【４，１０】

３，５，６，７，４，１０

第三趟：

３，５，６，７，４......

３，５，６，４，７

第四趟：

３，５，４，６

第五趟：

３，４，５，６，７

如此类推
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
vector<int> Bubble_Sort(vector<int>& nums) {
        for(int i = nums.size() - 1; i >= 0; i--){  //每一趟都决定了最后一个数是最大的
            int flag = 0;
            for(int j = 0; j < i ; j++){
                if(nums[j] > nums[j+1]){
                    int temp = nums[j];
                    nums[j] = nums[j+1];
                    nums[j+1] = temp;
                    flag = 1;         //标识发生了交换
                }
            }
            if(flag == 0)　　//全程无交换直接退出
                break;
        }
        return nums;
    }

二、插入排序（稳定O(N)～O(N^2^) ）

默认手中已经拿着一个数字。

查看前一个数字是否比当前的数字大，如果是则把前面比它大的数往后移一位，最后把当前元素放到空位即可。

最好情况：顺序　T = O(N)

最坏情况：逆序　T = O(N^2^) ｎ数字都要移动一位，一共移动n次。

３４，８，６４，５１，３２，２１

８，３４，６４，５１，３２，２１ (移动１次)

８，３４，６４，５１，３２，２１

８，３４，５１，６４，３２，２１ (移动１次)

８，３２，３４，５１，６４，２1 (移动３次)

８，２１，３２，３４，５１，６４　(移动４次)

1
2
3
4
5
6
7
8
9
10
11
vector<int> Insertion_Sort(vector<int>& nums) {
        int p,i,tmp;
        for(p = 1; p < nums.size(); p++){
            tmp = nums[p];
            for(i = p; i > 0 && nums[i-1] > tmp; i--){
                nums[i] = nums[i-1];
            }
            nums[i] = tmp;
        }
        return nums;
    }

三、希尔排序（不稳定）

对插入排序的改进，加入增量序列，以减少逆序对，内部用插入排序进行交换元素

Hibbard增量序列　D = 2^K - 1 (相邻元素互质)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
vector<int> Shell_Sort(vector<int>& nums) {
    int i,j,d,tmp;
    int n = nums.size();
    for(d = n/2; d > 0; d /= 2){
        for(i = d; i < n; i++){
            tmp = nums[i];
            for(j = i; j >= d && nums[j-d] > tmp; j -= d){
                nums[j] = nums[j-d];
            }
            nums[j] = tmp;
        }
    }
    return nums;
}

四、选择排序（不稳定 N^2^）

思路：找出集合中最小的数，与当前的数交换

或者找到最大值，和最后一个数作交换

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
vector<int> sortArray(vector<int>& nums) {
        int mini,tmp;
        for(int i = 0; i < nums.size(); i++){
            mini = i;
            for(int j = i; j < nums.size(); j++){
                if(nums[j] < nums[mini])
                    mini = j;
            }
            if(i != mini){           //找出最小的数不是当前元素，则交换
                tmp = nums[i];
                nums[i] = nums[mini];
                nums[mini] = tmp;
            }
        }   
        return nums;
    }

五、堆排序（不稳定 nlogn）

首先把数构建成一个大根堆，是一个hepify的过程，从上往下。

堆需要满足２条件：

  • 是一棵完全二叉树（从左到右，从上到下生成）

  • 堆里面的父节点的值>子节点的值

把一个杂乱的数弄成一个最大堆，从第n/2个结点开始检查其子节点是否均小于父节点，如此类推往下推上去，

可用数组来存储完全二叉树的每个结点的值，因为每个结点是连着的，且能通过公式计算出该结点的父节点的下标，如现在结点下标为i，则parent = (i - 1) / 2,cl = i*2+1,cr = i*2+2 ,向下取整。

假设建立大根堆：

1、build_heap：从最后一个结点的parent结点开始，根据下标倒着进行heapify。

2、heapify：把最大的数字放到顶部。这时候堆的稳定结构被破坏，又需要重复做heapify

3、建立堆之后，即可做堆排序heap_sort：heapify之后得到堆顶的值是最大的，因此把它和叶子最后一个结点交换（10和2），交换完堆的结构又变得不稳定，因此继续做heapify

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
void swap(int tree[], int i, int j){
    int tmp = tree[i];
    tree[i] = tree[j];
    tree[j] = tmp;
}

//heapify 把一个最大的结点放到最前，然后对交换下来的点做heapify，以保持大根堆的结构（大根堆）
//n是树上元素的个数，i表示从第i个结点开始heapify
void heapify(int tree[], int n, int i){ 
    if(i >= n){
        return;
    }
    int c1 = 2 * i + 1;
    int c2 = 2 * i + 2;
    int maxn = i;
    if(c1 < n && tree[c1] > tree[maxn]){
        maxn = c1;
    }
    if(c2 < n && tree[c2] > tree[maxn]){
        maxn = c2;
    }
    if(maxn != i){
        swap(tree, maxn, i);
        heapify(tree, n, maxn);  //对交换后的结点进行heapify
    }
}

//建立堆
//假如是杂乱无章的数字，要从最后一个结点的parent结点开始，根据下标倒着进行堆化（3->2->1->0），就是图中的3
void build_heap(int tree[], int n){  
    int last_node = n - 1;
    int parent = (last_node - 1) / 2;
    for(int i = parent; i >= 0; i--){
        heapify(tree, n, i);
    }
}

//堆排序
void heap_sort(int tree[], int n){
    build_heap(tree, n);
    for(int i = n - 1; i >= 0; i--){
        swap(tree, i, 0);
        heapify(tree, i, 0); //每次从第0个结点开始做heapify
    }
}

int main()
{
    int tree[] = {2, 5, 3, 1, 10, 4};
    int n = 6;
    heap_sort(tree, n);
    for(int i = 0; i < n; i++){
        cout << tree[i] <<endl;
    }
    return 0;
}

六、归并排序（稳定 nlogn）

归并排序(Merge Sort)采用分治法的思想，通过分治把每个子序列有序，当分出来的小组只剩下一个元素时，可以认为该区间有序，便合并相邻的２个小组。

若将2个有序的序列合并成为有序列表，称为二路归并

**Merge(int arr[], int l, int m, int r) **的作用是，假设已有两个有序的数组，要对其进行合并。

使用双指针，把每个小的元素放到原序列中，直到最后把剩下的元素都放进去。

**mergeSort(int arr[], int l, int r)**的作用是递归地分裂小组，直到剩下一个，再把相邻小组合并。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
void Merge(int arr[], int l, int m, int r){ 
    int left_size = m - l;
    int right_size = r - m + 1;
    int left[left_size];
    int right[right_size];
    int i,j,k;
  	//将排好序的左半部分放到左数组
    for(i = l; i < m; i++){	
        left[i - l] = arr[i];
    }
  	//将排好序的左半部分放到左数组
    for(i = m; i <= r; i++){
        right[i - m] = arr[i];
    }
  
    i = 0, j = 0, k = l;
		//Merge into the original array （实际用了双指针）
    while(i < left_size && j < right_size){
        if(left[i] < right[j]){
            arr[k++] = left[i];
            i++;
        }
        else{
            arr[k++] = right[j];
            j++;
        }
    }
  
		//put the rest of elements into array
    while(i < left_size){
        arr[k++] = left[i];
        i++;
    }

    while(j < right_size){
        arr[k++] = right[j];
        j++;
    }
}

void mergeSort(int arr[], int l, int r){
    if(l == r)
        return;
    else{
        int m = (l + r) / 2;
        mergeSort(arr, l, m);
        mergeSort(arr, m+1, r);
        Merge(arr, l, m+1, r);
    }
}

int main()
{
    int arr[] = {6,8,10,9,4,5,2,7};
    int l = 0;
   // int m = 4;
    int r = 7;
    mergeSort(arr, l, r);
    for(int i = 0; i <= r; i++){
        cout << arr[i] << endl;
    }
    return 0;
}

七、快速排序（不稳定On(nlog2n) ~O(n^2^ )）

(1)选择基准：在待排序列中，按照某种方式挑出一个元素，作为 “基准”（pivot）；
(2)分割操作：以该基准在序列中的实际位置，把序列分成两个子序列。此时，在基准左边的元素都比该基准小，在基准右边的元素都比基准大；
(3)递归地对两个序列进行快速排序，直到序列为空或者只有一个元素。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <iostream>
using namespace std;
void quickSort(int arr[], int left, int right) {
    if(left < right) {
        int i = left, j = right;
        int key = arr[left];
        while(i < j) {
            while(arr[j] > key && i < j) j--;
            if(i < j) {
                arr[i] = arr[j];
                i++;
            } 
            while(arr[i] < key && i < j) i++;
            if(i < j) {
                arr[j] = arr[i];
                j--;
            }
        }
        arr[i] = key;
        quickSort(arr, left, i - 1);
        quickSort(arr, i + 1, right);
    }
}

int main()
{
    int arr[9] = {3,5,8,1,2,9,4,7,6};
    quickSort(arr,0,8);
    for(int i = 0; i < 9; i++){
        cout << arr[i] << " " << endl;
    }
}

『顺序数组』和『逆序数组』上会导致递归树的高度增加（非常不平衡、递归树倾斜），这时快排的时间复杂度会退化成O(n^2^ )，因此可以随机获取pivot数，以打破这种顺序性。

1
int randomIdx = rand() % (right - left + 1) + left; //取[left, right]之间的随机数

使用场景

  1. n较小(n <= 50) ，可选用插入排序或者选择排序
  2. 若文件初始状态基本有序，可采用插入、冒泡、快速排序
  3. n较大，可考虑快速排序、堆排序、归并排序
FEATURED TAGS
算法
FRIENDS