交换类排序

本文主要是介绍交换类排序，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

一、冒泡排序(Bubble Sort)

1.时间复杂度：O(n²)

2.空间复杂度：O(1)

 1 void BubbleSort(int* a, int num) {
 2     int i, j;
 3     for (i = 1; i <= num - 1; ++i) {
 4         for (j = 1; j <= num - i; ++j) {
 5             if (a[j] > a[j + 1]) {//前后交换
 6                 a[0] = a[j];
 7                 a[j] = a[j + 1];
 8                 a[j + 1] = a[0];
 9             }
10         }
11     }
12 }

二、快速排序(Quick Sort)

1.时间复杂度：O(nlog₂n)

2.空间复杂度：O(log₂n)

3.实现：

 1 int Patition(int* a, int low, int high) {
 2     a[0] = a[low];
 3     while (low < high) {
 4         while (low < high && a[high] >= a[0]) {
 5             high--;
 6         }
 7         a[low] = a[high];//将比枢轴记录小的记录移到低端
 8         while (low < high && a[low] <= a[0]) {
 9             low++;
10         }
11         a[high] = a[low];//将比枢轴记录大的记录移到高端
12     }
13     a[low] = a[0];//枢轴记录到位
14     return low;//返回枢轴位置
15 }
16 
17 void QuickSort(int* a, int low, int high) {
18     int pos;
19     if (low < high) {
20         pos = Patition(a, low, high);//枢轴位置
21         QuickSort(a, pos + 1, high);//右区间
22         QuickSort(a, low, high - 1);//左区间
23     }
24 }

三、源代码

 1 //在 Microsoft Visual Studio Community 2022 下测试通过
 2 #define _CRT_SECURE_NO_WARNINGS
 3 #include <stdio.h>
 4 
 5 void BubbleSort(int* a, int num) {
 6     int i, j;
 7     for (i = 1; i <= num - 1; ++i) {
 8         for (j = 1; j <= num - i; ++j) {
 9             if (a[j] > a[j + 1]) {//前后交换
10                 a[0] = a[j];
11                 a[j] = a[j + 1];
12                 a[j + 1] = a[0];
13             }
14         }
15     }
16 }
17 
18 int Patition(int* a, int low, int high) {
19     a[0] = a[low];
20     while (low < high) {
21         while (low < high && a[high] >= a[0]) {
22             high--;
23         }
24         a[low] = a[high];//将比枢轴记录小的记录移到低端
25         while (low < high && a[low] <= a[0]) {
26             low++;
27         }
28         a[high] = a[low];//将比枢轴记录大的记录移到高端
29     }
30     a[low] = a[0];//枢轴记录到位
31     return low;//返回枢轴位置
32 }
33 
34 void QuickSort(int* a, int low, int high) {
35     int pos;
36     if (low < high) {
37         pos = Patition(a, low, high);//枢轴位置
38         QuickSort(a, pos + 1, high);//右区间
39         QuickSort(a, low, high - 1);//左区间
40     }
41 }
42 
43 int main(void) {
44     int i;
45     int a[11] = { 0, 9, 4, 8, 3, 1, 6, 7, 0, 2, 5 };//a[0]设为监视哨
46     //BubbleSort(a, 10);
47     QuickSort(a, 1, 10);
48     for (i = 1; i < 11; ++i) {
49         printf("%d ", a[i]);
50     }
51     return 0;
52 }

这篇关于交换类排序的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！