快速排序与冒泡排序以及代码

快速排序

快速排序（Quicksort）是一种常用的排序算法，它基于分治的思想。
时间复杂度：O（nlogn）
空间复杂度：O（logn）

快速排序的基本思想如下：

1. 选择一个元素作为基准（pivot）。
2. 将序列中比基准小的元素移到基准的左边，比基准大的元素移到基准的右边。这个过程称为划分（partition）。
3. 对划分后的两个子序列（基准左边和右边的序列）递归地应用上述步骤，直到子序列的长度为1或0，也即序列已经有序。
4. 合并所有子序列的结果，得到最终的排序序列。

代码参考这篇文章：

void Quick_Sort(int *arr, int begin, int end) {
	if (begin > end) {     //当待排序的子数组长度为0或负数时，终止递归 
		return;
	}
	int tmp = arr[begin];  //取数组的第一个元素arr[begin]作为基准元素
	int i = begin;
	int j = end;
	while(i != j) {  	   //指针i和j分别从数组的两端向中间移动，寻找可以交换的元素
		while(arr[j] >= tmp && j > i)
			j--;
		while(arr[i] <= tmp && j > i)
			i++;
		if(j > i) {  
			int t = arr[i];
			arr[i] = arr[j];
			arr[j] = t;
		}
	}
	arr[begin] = arr[i];
	arr[i] = tmp;       //将基准元素放在最终位置
	Quick_Sort(arr, begin, i-1);
	Quick_Sort(arr, i+1, end); 
} 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

冒泡排序

冒泡排序是一种简单但效率较低的排序算法。它通过多次交换相邻元素的位置来实现排序。下面是冒泡排序的具体过程：

1.从数组的第一个元素开始，比较相邻的两个元素，如果前一个元素大于后一个元素，则交换它们的位置。
2.继续比较下一对相邻元素，重复上述比较和交换操作，直到遍历到倒数第二个元素。
3.重复执行步骤 1 和步骤 2，直到所有元素都被比较并排序。
这样，每一轮遍历都会将未排序部分的最大（或最小）元素移动到已排序部分的末尾。因此，经过多轮遍历后，整个数组就会按照升序（或降序）排列。
1
2
3
4
5
6

写代码时有个细节要注意： for (int i = 0; i < size - 1; i++) {

#include 
using namespace std;

void bubbleSort(int arr[], int size) {
    for (int i = 0; i < size - 1; i++) { //size-1  而非size 因为要arr[j+1]
        for (int j = 0; j < size - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                // 交换 arr[j] 和 arr[j + 1] 的值
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

int main() {
    int arr[] = {5, 2, 8, 12, 1};
    int size = sizeof(arr) / sizeof(arr[0]);  //sizeof(arr) 表示整个数组 arr 在内存中占用的总字节数。sizeof(arr[0]) 表示数组 arr 中单个元素 arr[0] 的字节大小。

    cout << "排序前的数组：";
    for (int i = 0; i < size; i++) {
        cout << arr[i] << " ";
    }

    bubbleSort(arr, size);

    cout << "\n排序后的数组：";
    for (int i = 0; i < size; i++) {
        cout << arr[i] << " ";
    }

    return 0;
}

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