面向自由编程

排序算法大总结

Posted on Edited on In
Symbols count in article: 5.4k Reading time ≈ 5 mins.

总览

排序算法 平均时间复杂度 最好情况 最坏情况 辅助空间 稳定性
冒泡排序 $O(n^2)$ $O(n)$ $O(n^2)$ $O(1)$ √
选择排序 $O(n^2)$ $O(n^2)$ $O(n^2)$ $O(1)$ x
直接插入排序 $O(n^2)$ $O(n)$ $O(n^2)$ $O(1)$ √
归并排序 $O(n * \log(n))$ $O(n * \log(n))$ $O(n * \log(n))$ $O(n)$ √
快速排序 $O(n * \log(n))$ $O(n * \log(n))$ $O(n^2)$ $O(n * \log(n))$ x
堆排序 $O(n * \log(n))$ $O(n * \log(n))$ $O(n * \log(n))$ $O(1)$ x
希尔排序 $O(n^{1.3})$ $O(n)$ $O(n^{2})$ $O(1))$ x
计数排序 $O(n + k)$ $O(n + k)$ $O(n + k)$ $O(n + k)$ √
桶排序 $O(n + k))$ $O(n + k)$ $O(n + k)$ $O(n + k)$ √
基数排序 $O(d * (r + n))$ $O(d * (rd + n))$ $O(d * (r + n))$ $O(n + rd)$ √

n代表元素长度，r代表元素的基数个数，d代表基数长度, k为辅助数组长度

冒泡排序

  1. 比较相邻的元素。如果第一个比第二个大，就交换它们两个；
  2. 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，3. 这样在最后的元素应该会是最大的数；
  3. 针对所有的元素重复以上的步骤，除了最后一个；
  4. 重复步骤1~3，直到排序完成。

直接上代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
template<typename T>
void bubbleSort(vector<T>& nums){
    bool flag;
    int n = nums.size();
    for(int i = n - 1; i > 0; -- i){
        flag = true;
        for(int j = 0; j < i; ++ j){
            if(nums[j] > nums[i]) {
                swap(nums[j], nums[i]);
                flag = false;
            }
        }
        if(flag) break;
    }
}

冒泡排序思路简单，代码也简单，特别适合小数据的排序.

选择排序

在未排序的数列中找到最小(or最大)元素，然后将其存放到数列的起始位置；接着，再从剩余未排序的元素中继续寻找最小(or最大)元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
template<typename T>
void selectSort(vector<T>& nums){
    int n = nums.size();
    int minIndex;
    for(int i = 0; i < n; ++ i){
        minIndex = i;
        for(int j = i + 1; j < n; ++ j){
            if(nums[j] < nums[minIndex]){
                minIndex = j;
            }
        }
        swap(nums[i], nums[minIndex]);
    }
}

直接插入排序

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

1
2
3
4
5
6
7
8
9
10
11
12
13
template<typename T>
void insertSort(vector<T>& nums){
    int n = nums.size();
    for(int i = 1; i < n; ++ i){
        int key = nums[i];
            int j = i - 1;
            while(j >= 0 && key < nums[j]){
                nums[j + 1] = nums[j];
                -- j;
            }
            nums[j + 1] = key;
    }
}

归并排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
template<typename T>
void merge(vector<T>& nums, int l1, int r1, int l2, int r2){
    T temp[r2 - l1 + 1];
    int index = 0;
    int base = l1;
    while(l1 <= r1 && l2 <= r2){
        temp[index ++] = nums[l1] < nums[l2] ? nums[l1 ++] : nums[l2 ++];
    }
    while(l1 <= r1) temp[index ++] = nums[l1 ++];
    while(l2 <= r2) temp[index ++] = nums[l2 ++];
    for(int i = 0; i < index; ++ i){
        nums[base + i] = temp[i];
    }
}

template<typename T>
void mergeSort(vector<T>& nums, int left, int right){
    if(left < right){
        int mid = left + (right - left) / 2;
        mergeSort(nums, left, mid);
        mergeSort(nums, mid + 1, right);
        merge(nums, left, mid, mid + 1, right);
    }
}

快速排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
template<typename T>
int qsort(vector<T>& nums, int l, int r){
    int key = nums[l];
    while(l < r){
        while(l < r && nums[r] >= key) -- r;
        nums[l] = nums[r];
        while(l < r && nums[l] <= key) ++ l;
        nums[r] = nums[l];
    }
    nums[l] = key;
    return l;
}

template<typename T>
void quickSort(vector<T>& nums, int left, int right){
    if(left < right){
        int mid = qsort(nums, left, right);
        quickSort(nums, left, mid - 1);
        quickSort(nums, mid + 1, right);
    }
}

堆排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
template<typename T>
void adjust(vector<T>& nums, int len, int index){
    int cur = index;
    int lchild = (index << 1) + 1, rchild = (index << 1) + 2;
    if(lchild < len && nums[lchild] > nums[cur]) cur = lchild;
    if(rchild < len && nums[rchild] > nums[cur]) cur = rchild;
    if(cur != index){
        swap(nums[index], nums[cur]);
        adjust(nums, len, cur);
    }
}

template<typename T>
void heapSort(vector<T>& nums){
    int n = nums.size();
    for(int i = n / 2 - 1; i >= 0; -- i){
        adjust(nums, n, i);
    }
    for(int i = n - 1; i >= 1; -- i){
        swap(nums[0], nums[i]);
        adjust(nums, i, 0);
    }
}

希尔排序

1
2
3
4
5
6
7
8
9
10
11
12
13
template<typename T>
void shellSort(vector<T>& nums){
    int n = nums.size();
    for(int step = n / 2; step > 0; step /= 2){
        for(int i = step; i < n; i += step){
            for(int j = i - step; j > 0; j -= step){
                if(nums[j] > nums[j + step]){
                    swap(nums[j], nums[j + step]);
                }
            }
        }
    }
}

计数排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
template<typename T>
void countSort(vector<T>& nums){
    int maxv = *max_element(nums.begin(), nums.end()), minv = *min_element(nums.begin(), nums.end());
    int len = maxv - minv + 1;
    T cnt[len];
    memset(cnt, 0, sizeof(cnt));
    for(auto&& num : nums) ++ cnt[num - minv]; 
    int index = 0;
    for(int i = 0; i < len; ++ i){
        while(cnt[i] --){
            nums[index ++] = i + 1;
        }
    }
}

桶排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
template<typename T>
void bucketSort(vector<T>& nums){
    int n=nums.size();
    int maxv = *max_element(nums.begin(), nums.end());
    int minv = *min_element(nums.begin(), nums.end());
    int bucketCnt = (maxv - minv) / n + 1;
    vector<vector<T>> buckets(bucketCnt);
    for(auto& num : nums){
        int bucketIdx = (num - minv) / bucketCnt;
        if(bucketIdx >= bucketCnt) bucketIdx = bucketCnt - 1;
        buckets[bucketIdx].push_back(num);
    }
    nums.clear();
    for(auto& bucket : buckets){
        sort(bucket.begin(), bucket.end());
        for(int& num : bucket) nums.push_back(num);
    }
}

基数排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
void radixSort(vector<int>& nums){
    int n = nums.size();
    int minv = *min_element(nums.begin(), nums.end());
    for(auto&num:nums) num -= minv;
    int maxv = *max_element(nums.begin(), nums.end());
    int maxBit = 1,curNum = 10;
    while(curNum <= maxv){
        ++ maxBit;
        curNum *= 10;
    }
    vector<int> tmp(n);
    for(int i = 0, place = 1; i < maxBit; ++ i, place *= 10){
        vector<int> cnt(10);
        for(int j = 0; j < n; ++ j) ++ cnt[nums[j] / place % 10];
        for(int j = 1; j < 10; ++ j) cnt[j] += cnt[j - 1];
        for(int j = n - 1; j >= 0; -- j){
            int bitNum = nums[j] / place % 10;
            tmp[cnt[bitNum] - 1] = nums[j];
            -- cnt[bitNum];
        }
        copy(tmp.begin(),tmp.end(),nums.begin());
    }
    for(auto& num : nums) num += minv;
}