常用排序算法

发表于 | 分类于
字数统计: 1.9k | 阅读时长 ≈ 8
名称性能分析特点稳定性
直接插入时间：- 最好：O(n)，- 最差：O(n^2)；空间：O(1)适合元素基本有序的场景稳定
折半插入时间：- 最好：O(nlogn)，- 最差：O(n^2)；空间：O(1)适合元素较多的场景稳定
希尔排序时间：- 最好：O(n^1.5)，- 最差：O(n^2)；空间：O(1)不稳定
冒泡排序时间：- 最好：O(n)，- 最差：O(n^2)；空间：O(1)适合元素基本有序的场景稳定
快速排序时间：- 最好：O(nlogn)， - 最差：O(n^2)；空间：O(logn)序列越无序，效率越高；反之，效率越低不稳定
选择排序时间：O(n^2)；空间：O(1)不稳定
堆排序时间：O(nlogn)；空间：O(1)适合元素较多的场景不稳定
归并排序时间：O(nlogn)；空间：O(n)稳定

1.插入类排序

1.1 直接插入排序

算法思想：

  1. 逐个扫描，从后向前依次进行比较，
  2. 插入合适位置
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void inserSort(int *arr, int arrSize)
{ //插入排序
    int i, j, temp;
    for (i = 1; i < arrSize; ++i) //默认第一个元素有序，从第二个元素开始
    {
        temp = arr[i]; //将待插入的关键字存储在temp中
        j = i - 1;
        while (j >= 0 && temp < arr[j]) //从待插入的关键字向前扫描，将大于temp的元素向后移一位
        {
            arr[j + 1] = arr[j];
            --j;
        }
        arr[j + 1] = temp; //将待插入的关键字插入
    }
}

1.2 折半插入排序

算法思想：

  1. 引入上下标，非遍历，
  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
void binaryInsertSort(int *arr, int arrSize)
{ //折半插入排序
    int i, low, high, mid;
    low = 0, high = 0;
    for (i = 1; i < arrSize; ++i) //默认第一个元素有序，从第二个元素开始
    {
        while (low <= high)
        {
            mid = (low + high) / 2;     //mid向下取整
            if (arr[mid] > arr[i])      //arr[mid]大于待插入元素时，说明要向低半区插入
                high = mid - 1;         //更新high
            else if (arr[mid] < arr[i]) //arr[mid]小于待插入元素时，说明要向高半区插入
                low = mid + 1;          //更新low
        }
        //low > high时，跳出循环，开始插入元素
        int temp = arr[i]; //将待插入的关键字存储在temp中
        int j = i - 1;
        while (j >= mid && temp < arr[j])//从待插入的关键字向前扫描，将大于temp的元素向后移一位
        {
            arr[j + 1] = arr[j];
            --j;
        }
        arr[j + 1] = temp; //将待插入的关键字插入
    }
}

1.3 希尔排序

算法思路：

  1. 以固定增量将待排序列分成n组
  2. 进行组内排序；
  3. 选取更小的增量重复进行，直到增量为1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void shellSort(int *arr, int arrSize)
{ //希尔排序
    int h = 1;
    while (h < arrSize / 3)
        h = 3 * h + 1;
    while (h >= 1)
    {
        int i;
        for (i = h; i < arrSize; i++)
        {
            int j;
            for (j = i; j >= h && (arr[j] < arr[j - h]); j -= h)
            {
                int temp = arr[j];
                arr[j] = arr[j - h];
                arr[j - h] = temp;
            }
        }
        h /= 3;
    }
}

2.交换类排序

2.1 冒泡排序

算法思路：

  1. 将待排序列中的两个相邻元素进行比较，
  2. 每次都将较大(小)元素置前，以完成降(升)序排序
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void bubbleSort(int *arr, int arrSize)
{ //冒泡排序
    int i, j, temp, flag;
    for (i = arrSize - 1; i >= 1; --i)
    {
        flag = 0; //标记本趟是否发生交换
        for (j = 1; j <= i; ++j)
        {
            if (arr[j - 1] > arr[j])
            {
                temp = arr[j];
                arr[j] = arr[j - 1];
                arr[j - 1] = temp;
                flag = 1; //发生交换，flag = 1
            }
        }
        if (flag == 0) //如果没有发生交换，说明序列有序
            return;
    }
}

2.2 快速排序

算法思想：

  1. 引入头尾指针，以第一个元素为“轴”；
  2. 尾指针向前扫描，遇到比轴小的数时，放在头指针处；
  3. 变换扫描方向，头指针向后扫描，遇到比轴大的数时，放在尾指针处；
  4. 重复此过程，直到头尾指针相遇，即完成一次排序；
  5. 递归对轴的左右两部分分别进行此过程即可
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
void quickSortHelper(int *arr, int low, int high)
{//对arr[low]到arr[high]进行排序
    int temp;              //temp用于存储“轴”的值
    int i = low, j = high; //i为头指针，j为尾指针
    if (low < high)        //低位小于高位时，开始交换
    {
        temp = arr[low];
        while (i < j)
        {//将数组中小于temp的元素放在temp左边，大于temp的元素放在temp右边
            while (j > i && arr[j] >= temp) //从右向左扫描，找到一个小于temp的元素
                --j;
            if (i < j)
            {
                arr[i] = arr[j]; //将元素放在temp左边
                ++i;             //头指针右移
            }
            while (i < j && arr[i] < temp) //从左向右扫描，找到一个大于temp的元素
                ++i;
            if (i < j)
            {
                arr[j] = arr[i]; //将元素放在temp右边
                --j;             //尾指针右移
            }
        }
        arr[i] = temp;                     //将temp放在最终位置
        quickSortHelper(arr, low, i - 1);  //递归排序temp左边
        quickSortHelper(arr, i + 1, high); //递归排序temp右边
    }
}

void quickSort(int *arr, int arrSize)
{ //快速排序
    quickSortHelper(arr, 0, arrSize - 1);
}

3.选择类排序

3.1 简单选择排序

算法思想：

  1. 找出无序序列中的最小关键字；
  2. 与第一个关键字进行位置交换；
  3. 循环此过程以遍历整个序列
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void selectSort(int *arr, int arrSize)
{ //简单选择排序
    int i, j, k, temp;
    for (i = 0; i < arrSize; i++)
    {
        k = i;
        //从无序序列中挑出最小的关键字
        for (j = i + 1; j < arrSize; ++j)
            if (arr[k] > arr[j])
                k = j;
        //将最小关键字与无序序列的第一个关键字交换
        temp = arr[i];
        arr[i] = arr[k];
        arr[k] = temp;
    }
}

3.2 堆排序

算法思想：

  1. 建堆；
    1. 大根堆：升序排序
    2. 小根堆：降序排序
  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
void heapify(int *arr, int i, int len)
{ //建堆
    //标记左右孩子、最大节点的序号
    int left = 2 * i + 1;
    int right = 2 * i + 2;
    int largest = i;
    if (left < len && arr[left] > arr[largest])
        largest = left;
    if (right < len && arr[right] > arr[largest])
        largest = right;
    if (largest != i)
    { //父节点不是最大节点时进行调整
        swap(arr, i, largest);
        heapify(arr, largest, len);
    }
}

void heapSort(int *arr, int arrSize)
{ //堆排序
    int i;
    for (i = arrSize / 2; i >= 0; i--) //建堆
        heapify(arr, i, arrSize);
    for (i = arrSize - 1; i > 0; i--)
    {
        swap(arr, 0, i);    //最后一个节点与根节点交换
        heapify(arr, 0, i); //剩余节点重新建堆
    }
}

4. 归并排序

算法思想：

  1. 将待排序列看作一元组;
  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
33
34
35
36
37
38
39
void merge(int *arr, int low, int mid, int high, int *help)
{ //使arr[low]到arr[mid]与arr[mid]到arr[high]有序
    int i = low, j = mid + 1;
    while (i <= mid || j <= high) //循环直到所有元素排序完毕
    {
        if (j <= high && (arr[i] >= arr[j] || i > mid))
        { //m[i] >= m[j]或者前半段已完全排序,而后半段未完全排序的情况
            help[i - low + j - mid - 1] = arr[j];
            j++;
        }
        else if (i <= mid || j > high)
        { //m[i] < m[j]或后半段已完全排序而前半段未完全排序的情况
            help[i - low + j - mid - 1] = arr[i];
            i++;
        }
    }
    for (i = low; i <= high; i++) //将排序好的值赋值给原数组
        arr[i] = help[i - low];
}

void mergeSortHelper(int *arr, int low, int high, int *help)
{
    if (low < high)
    {
        int mid = (low + high) / 2;
        //递归对左右部分进行归并排序，这里体现了二路归并排序
        mergeSortHelper(arr, low, mid, help);
        mergeSortHelper(arr, mid + 1, high, help);
        //使arr数组的前后两部分有序
        merge(arr, low, mid, high, help);
    }
}

void mergeSort(int *arr, int arrSize)
{ //归并排序
    //辅助数组，提供额外空间
    int help[arrSize];
    mergeSortHelper(arr, 0, arrSize - 1, help);
}