1.冒泡排序
1.1.算法思想
从后往前两两比较相邻元素的值，若为逆序，则交换，直到序列比较完
1.由于总是将相邻两个元素中较小的放在最前面
2.因此进行一趟冒泡以后，最左边的元素一定是最小的
3.采取递归的思想，第一轮对0-7的元素冒泡，结束后0处是最小元素
4.第二轮对1-7的元素冒泡，本轮结束后1是剩下元素中最小的
5.第三轮对2-7冒泡，这样2处的是整个列表第三小的元素
6.如此递归下去，直到对长度为1的子序列递归，这时触发递归终止条件，排序结束
（或若某次排序过程中没有发生交换，则说明数组中的元素已经整体有序，排序结束）
1.2.代码
//交换 void swap(int &a, int &b) { int temp = a; a = b; b = temp; } //冒泡排序 void BubbleSort(int arr[], int n) { for (int i = 0; i < n - 1; i++) { //标记此轮循环中是否进行了交换 bool flag = false; //每次从数组中最后一个元素向前遍历，直到第i个元素 for (int j = n - 1; j >= i; j--) { //将相邻两个逆序元素交换为正序，并更改flag if (arr[j - 1] > arr[j]) { swap(arr[j - 1], arr[j]); flag = true; } }//for //此次循环元素都是正序，则结束函数 if (!flag) return; }//for }
1.3.时间复杂度和稳定性
1.空间复杂度：O（1）
2.时间复杂度：
①最好情况：有序，比较次数n - 1，交换次数0，因此，O（n）
②最坏情况：逆序，比较次数 = 交换次数 = (n-1) + (n - 2) + ... + 1 ，O（n^2）
3.稳定性：只有当前元素的前一个元素更大的时候才交换，相等不交换，因此，该算法稳定
if (arr[j - 1] > arr[j]) swap(arr[j - 1], arr[j]);
4.适用：链表和顺序表
2.快速排序
2.1.算法思想
1.取当前表中的第一个元素（也可以是任取）为基准元素，找到它在表中的位置，即左边元素都小于它，右边元素都大于等于它，这样基准元素就确定了它在数组中的最终位置
2.以它为分割，依次到它的左表和右表进行1操作
3.重复12，直到每个表都只有一个元素为止，则整个表都有序
2.2.代码
low指针的左边都小于基准元素，high指针的右边都大于等于基准元素
1.选取49为基准元素→low当前元素为空→high指向元素49 ≥ 基准元素49，不需要移动，high--
2.high当前指向元素27 < 49→27交换到low指针指向的位置，high空
3.low当前指向元素27 < 49→low++
4.low当前指向元素38 < 49→low++
5.low当前指向元素65 > 49→65交换到high指针指向的位置，low空
6.high指向的元素65 > 49→high--
7.high指向元素13 < 49→13交换到low指针指向的位置，high空
8.low指向元素13 < 49→low++
9.low指向元素97 > 49→97交换到high指针指向的位置，low空
10.high指向元素97 > 49→high--
11.high指向元素76 > 49→high--
12.high和low指向同一元素，49插入此元素
13.对左子表划分，取27为基准元素
14.high指向元素13 > 27→13交换到low指针指向的位置，high空
15.low指向元素为13 < 27→low++
16.low指向元素为38 > 27→27交换到high指针指向的位置，low空
17.high指向元素为38 > 27→high--
18.high和low指向同一元素，27插入此元素
19.27的左右子表都为1，则不需要继续排序；对49的右子表排序，取76为基准元素
20. high指向的元素为49 < 76→49交换到low指针指向的位置，high空
21.low指向的元素为49 < 76→low++
22.low指向的元素为97 > 76，97交换到high指针指向的位置，low空
23.high指向的元素为97 > 76，high--
24.high指向的元素为65 < 76，65交换到low指针指向的位置，high空
25.low指向的元素为65 < 76，low++
26.low，high指向同一元素，将76插入此元素
27.76的左子表长度为2，去左子表继续排序，取49为基准元素
28.high指向元素65 > 49，high--
29.high，low指向同一元素，将49插入此元素
int Partition(int arr[], int low, int high){ //选取第一个元素作为基准元素 int pivot = A[low]; //循环直到low = high while (low < high){ //当前元素比基准元素小时，将此元素移动到low指向的位置 while (low < high && arr[high] >= pivot) high--; arr[low] = arr[high]; //当前元素比基准元素大时，将此元素移动到high指向的位置 while (low < high && arr[low] < pivot) low++; arr[high] = arr[low]; } arr[low] = pivot; return low; } //快速排序 void QuickSort(int arr[], int low, int high){ if (low < high){ //划分左右子表 int pivotPos = Partition(arr, low, high); //左子表排序 QuickSort(arr, low, pivotPos - 1); //右子表排序 QuickSort(arr, pivoPos + 1, high); } }
2.3.时间复杂度和稳定性
1.时间复杂度：O（n）* 递归深度（与二叉树树形类似）
①最好时间复杂度 O（nlogn）
②快时间复杂度 O（n^2）本来就有序，每次的划分很不均，递归深度小
2.空间复杂度：O（递归层数）
①已经有序：O（n^2）
②二分：O（logn）
3.稳定性：不稳定
4.适用：顺序表
3.王道课后题
//交换元素 void swap(int &i, int &j) { int temp = i; i = j; j = temp; } //冒泡排序 void BubbleSort(int arr[], int n) { int i = 1, head = 0, tail = n - 1; for (i = 1; i <= n; i++) { //奇数次排序 if (i % 2) { for (int j = head; j < tail; j++) { if (arr[j] > arr[j + 1]) swap(arr[j], arr[j + 1]); } head++; } //偶数次排序 else { for (int j = tail; j > head; j--) { if (arr[j] < arr[j - 1]) swap(arr[j], arr[j - 1]); } tail--; } }//for }
时间最少——快速排序
void QuickSort(int arr[], int low, int high){ //pivot保存low的当前元素 int temp = arr[low]; while (low < high) { //high的当前元素不是偶数，则移动到low while (low < high && (arr[high] % 2)) high--; arr[low] = arr[high]; //low的当前元素不是偶数，则移动到high while (low < high && !(arr[low] % 2)) low++; arr[high] = arr[low]; } //将temp赋值给low arr[low] = temp; }
//交换函数 void swap(int &a, int &b){ int temp = a; a = b; b = temp; } //划分和排序 void Partition(int arr[], int low, int high){ int pivot = random() % (high - low + 1); swap(arr[low], arr[pivot]); pivot = arr[low]; while (low < high){ while (low < high && arr[high] >= arr[pivot]) high--; arr[low] = arr[high]; while (low < high && arr[low] <= arr[pivot]) low++; arr[high] = arr[low]; } arr[low] = pivot; return low; } //函数入口 void QuickSort (int arr[], int low, int high) { if (low < high){ int qivot = Partition(arr, low, high); QuickSort(arr, low, qivot - 1); QuickSort(arr, qivot + 1, high); } }
//划分并且排序 int Partition(int arr[], int low, int high) { int pivot = arr[low]; while (low < high) { while (low < high && arr[high] >= pivot) high--; arr[low] = arr[high]; while(low < high&& arr[low] <= pivot) low++; arr[high] = arr[low]; } arr[low] = pivot; return low; } //快速函数入口 int QuickSort_SearchK(int arr[], int low, int high, int k) { if (low < high) { int pivot = Partition(arr, low, high); //返回的数组下标为k，即为第k小元素 if (pivot == k) return arr[pivot]; //返回数组下标大于k，去左子表 else if (pivot > k) return QuickSort_SearchK(arr, low, pivot - 1, k); //返回数组下标小于k，去右子表 else if (pivot < k) return QuickSort_SearchK(arr, pivot + 1, high, k); } //返回-1表示没找到 return -1; }
int QuickSort_SearchK(int arr[], int low, int high, int k){ int low_temp = low, high_temp = high, pivot = arr[low]; //快速排序算法实现 while (low < high) { while (low < high && arr[high] >= pivot) high--; arr[low] = arr[high]; while (low < high && arr[low] <= pivot) low++; arr[high] = arr[low]; } arr[low] = pivot; //判断是否当前元素在数组中的位置是否与k相等 //相等则是第k小元素 if (low == k) return arr[low]; //小于则去右子表查找 else if (low < k) return QuickSort_SearchK(arr, low_temp, low - 1, k); //大于则去左子表查找 else if (low > k) return QuickSort_SearchK(arr, low + 1, high_temp, k); }
//交换数组元素 void swap(int& a, int& b) { int temp = a; a = b; b = temp; } //0指代红，1指代白，2指蓝 void ColourSort(int arr[], int n) { int i = 0, h = 0, t = n - 1; //循环直到 i >= 尾指针t while (i < t) { //当前元素为0，与头指针交换 if (arr[i] == 0) { swap(arr[i], arr[h]); h++; } //当前指针为2，与尾指针交换 else if (arr[i] == 2) { swap(arr[i], arr[t]); t--; } //当前为白，往前移动一个元素 else i++; } }
1.使用快速排序排序数组A，快速排序特性：每轮确定一个元素在数组中的按顺序排列的大小位置
若n为奇数：n1 = n2 - 1，且A1的元素为A的数组下标0 - n1元素；n2为剩下元素
若n为偶数：n1 = n2，且A1的元素为A的数组下标0 - n1元素；n2为剩下元素
2.
//划分并排序 int QuickSort_Divide (int arr[], int n) { int low = 0, high = n - 1; //标记是否找到第n / 2小的元素 bool flag = false; int high_temp = high, low_temp = low; int pivot = arr[low]; while (!flag) { int pivot = arr[low]; while (low < high) { while (low < high && arr[high] >= pivot) high--; arr[low] = arr[high]; while (low < high && arr[low] <= pivot) low++; arr[high] = arr[low]; } arr[low] = pivot; if (low == n / 2) flag = true; //当前元素并非n/2，更小则去右子表，更大则去左子表 //更新low，high，low_temp，high_temp else if (low < n / 2) { high = high_temp; low_temp = low + 1; low = low_temp; } else if (low > n / 2) { low = low_temp; high_temp = low - 1; high = high_temp; } }//while int s1 = 0, s2 = 0; for (int i = 0; i < n / 2; i++) s1 += arr[i]; for (int i = n / 2; i < n; i++) s2 += arr[i]; return s2 - s1; }
