排序算法做个复习总结

(待更新)

基本排序算法

排序法 最差时间分析 平均时间复杂度 稳定度 空间复杂度
冒泡排序 O(n2) O(n2) 稳定 O(1)
选择排序 O(n2) O(n2) 稳定 O(1)
快速排序 O(n2) O(n*log2n) 不稳定 O(log2n)~O(n)
二叉树排序 O(n2) O(n*log2n) 不稳定 O(n)
插入排序 O(n2) O(n2) 稳定 O(1)
堆排序 O(n*log2n) O(n*log2n) 不稳定 O(1)
希尔排序 O O 不稳定 O(1)
归并排序 O(nlog n)

选择排序和冒泡排序相比较,比较次数基本一致.交换次数少了.

选择排序

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
#include<iostream>
using namespace std;
int main() {
     int nums[] = { 55, 18 , 33 , 22 , 6, 23 };
     int numslen = sizeof(nums) / sizeof(int);
     int temp = 0;
     int min = nums[0];
     int minIndex = 0;
     for(int i = 0 ; i < numslen - 1; i++){
         for (int j = i + 1; j < numslen - i; j++){
            if(nums[j] > min){
                min = nums[j];
                minIndex = j;
            }
         }
         //少比较一次
         if(minIndex > i){
           temp = nums[minIndex];
           nums[minIndex] = nums[i];
           nums[i] = temp;
     }
     cout << "选择排序后:" << endl;
     for(int i = 0 ; i < numslen ; i++){
         cout << nums2[i] << "\t";
     }
     return 0;
    }

冒泡排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<iostream>
    using namespace std;
    int main() {
     int nums2[] = { 55, 18 , 33 , 22 , 6, 23 };
     int numslen = sizeof(nums) / sizeof(int);
     int temp2 = 0;
     for(int i = 0 ; i < numslen - 1; i++){
         for (int j = 0; j < numslen - i - 1; j++){
            if(nums2[j] > nums2[j+1]){
                temp2 = nums2[j];
                nums2[j] = nums2[j+1];
                nums2[j+1] = temp2;
            }
         }
     }
     cout << "冒泡排序后:" << endl;
     for(int i = 0 ; i < numslen ; i++){
         cout << nums2[i] << "\t";
     }
    return 0;
}