在LeetCode刷题时,时常会遇到需要手动排序的题目. 对于一些较为复杂的排序方式有时会需要花时间去思考. 因此,在此记录几种经典的排序算法帮助回顾.(C语言. 升序排列)


1. 冒泡排序

思想: 犹如汽水的泡泡一样,一下升到水面上. 即每次遍历都通过两两比较的方式将最大(最小)的元素给移动到此次遍历范围的最边缘(“冒出去”).

平均时间复杂度: O(n2)

空间复杂度: O(1)

稳定性: 稳定

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void bubble_sort(int* nums, int numsSize)
{
    int temp = 0;
    
    for (int i = 0; i < numsSize - 1; i++)
    {
        for (int j = 0; j < numsSize - 1 - i; j++)
        {
            if (nums[j] > nums[j + 1])
            {
                temp = nums[j];
                nums[j] = nums[j + 1];
                nums[j + 1] = temp;
            }
        }
    }
}

2. 快速排序

思想: 先挖一个坑(基准值,默认索引为0),然后依索引从大到小先找小于这个坑的元素,换过来,这样坑就到了替换的过来的元素那里,再索引从小到大找大于这个坑的,换过来,如此反复,若索引相遇,则说明此时坑(基准值)的左边全为小于坑(基准值)的元素,右边全为大于坑(基准值)的元素,再使用递归对两边继续挖坑,完成排序.

平均时间复杂度: O(nlog2n)

空间复杂度: O(nlog2n)

稳定性: 不稳定

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
void quick_sort(int* nums, int l, int r)
{
    if (l < r)
    {
        int i = l, j = r, x = nums[l];
        while (i < j)
        {
            while(i < j && nums[j] >= x) // 从右向左找第一个小于x的数
                j--;  
            if(i < j) 
                nums[i++] = nums[j];
            
            while(i < j && nums[i] < x) // 从左向右找第一个大于等于x的数
                i++;  
            if(i < j) 
                nums[j--] = nums[i];
        }
        nums[i] = x;
        quick_sort(nums, l, i - 1); // 递归调用 
        quick_sort(nums, i + 1, r);
    }
}

3. 选择排序

思想: 第一次遍历比较 n - 1 次将最小的放到第一个,第二次遍历 n - 2 次将最小的放到第二个,依次类推,直至排序完成.

平均时间复杂: O(n2)

空间复杂度: O(1)

稳定性: 不稳定

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void select_sort(int* nums, int numsSize)
{
    int index = 0;
    int temp = 0;
    
    for (int i = 0; i < numsSize - 1; i++)
    {
        index = i;
        for (int j = i + 1; j < numsSize; j++)
        {
            if (nums[j] < nums[index])
            {
                index = j;
            }
        }
        if (index != i)
        {
            temp = nums[i];
            nums[i] = nums[index];
            nums[index] = temp;
        }
    }
}

4. 插入排序

思想: 在首个元素构建已排序序列,而后对于未排序的序列,在已排序的序列中从后向前扫描,并在合适的位置插入即可.

平均时间复杂: O(n2)

空间复杂度: O(1)

稳定性: 稳定

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void insert_sort(int* nums, int numsSize)
{   
    int cur = 0;
    int pos = 0;
    
    for (int i = 1; i < numsSize; i++)
    {
        cur = nums[i];
        pos = i - 1;
        while (pos >= 0 && cur < nums[pos])
        {
            nums[pos + 1] = nums[pos];
            pos--;
        }

        nums[pos + 1] = cur;
    }
}