人工智能-项目实践-数据结构-冒泡排序；直接插入排序；希尔排序；快速排序；堆排序；归并排序；基数排序.zip

#include <iostream> #include <vector> using namespace std; // 基础冒泡排序 vector<int> bubbleSort_1(vector<int> list){ vector<int> result; if (list.empty()){ return result; } result = list; int temp; // 要遍历的次数 for (int i = 0; i < result.size() - 1; ++i){ cout << "第" << i + 1 << "趟排序:" << endl;; // 从后向前依次的比较相邻两个数的大小 for (int j = 0; j < result.size() - 1; j++){ // 如果后面的元素小，则交换它们的位置 if (result[j + 1] < result[j]){ temp = result[j + 1]; result[j + 1] = result[j]; result[j] = temp; } cout << "排序中:"; for (int s = 0; s < result.size(); s++){ cout << result[s] << " "; } cout << endl; } cout << "排序结果:"; for (int s = 0; s < result.size(); s++){ cout << result[s] << " "; } cout << endl; } return result; } // 优化冒泡排序 vector<int> bubbleSort_2(vector<int> list){ vector<int> result; if (list.empty()){ return result; } result = list; int temp; // 要遍历的次数 for (int i = 0; i < result.size() - 1; ++i){ cout << "第" << i + 1 << "趟排序:" << endl;; //交换标志位 bool bChanged = false; // 从后向前依次的比较相邻两个数的大小 for (int j = 0; j < result.size() - 1; j++){ // 如果后面的元素小，则交换它们的位置 if (result[j + 1] < result[j]){ temp = result[j + 1]; result[j + 1] = result[j]; result[j] = temp; bChanged = true; } cout << "排序中:"; for (int s = 0; s < result.size(); s++){ cout << result[s] << " "; } cout << endl; } // 如果标志为false，说明本轮遍历没有交换，已经是有序数列，可以结束排序 if (false == bChanged){ break; } cout << "排序结果:"; for (int s = 0; s < result.size(); s++){ cout << result[s] << " "; } cout << endl; } return result; } // 直接插入排序 vector<int> insertSort(vector<int> list){ vector<int> result; if (list.empty()){ return result; } result = list; // 第1个数肯定是有序的，从第2个数开始遍历，依次插入有序序列 for (int i = 1; i < result.size(); i++){ // 取出第i个数，和前i-1个数比较后，插入合适位置 int temp = result[i]; // 因为前i-1个数都是从小到大的有序序列，所以只要当前比较的数(list[j])比temp大，就把这个数后移一位 int j = i - 1; for (j; j >= 0 && result[j] > temp; j--){ result[j + 1] = result[j]; } result[j + 1] = temp; } return result; } // 希尔排序 vector<int> ShellSort(vector<int> list){ vector<int> result = list; int n = result.size(); for (int gap = n >> 1; gap > 0; gap >>= 1){ for (int i = gap; i < n; i++){ int temp = result[i]; int j = i - gap; while (j >= 0 && result[j] > temp){ result[j + gap] = result[j]; j -= gap; } result[j + gap] = temp; } for (int i = 0; i < result.size(); i++){ cout << result[i] << " "; } cout << endl; } return result; } // 快速排序的division函数 int division(vector<int> &list, int left, int right){ // 以最左边的数(left)为基准 int base = list[left]; while (left < right) { // 从序列右端开始，向左遍历，直到找到小于base的数 while (left < right && list[right] >= base) right--; // 找到了比base小的元素，将这个元素放到最左边的位置 list[left] = list[right]; // 从序列左端开始，向右遍历，直到找到大于base的数 while (left < right && list[left] <= base) left++; // 找到了比base大的元素，将这个元素放到最右边的位置 list[right] = list[left]; } // 最后将base放到left位置。此时，left位置的左侧数值应该都比left小； // 而left位置的右侧数值应该都比left大。 list[left] = base; return left; } // 快速排序 void QuickSort(vector<int> &list, int left, int right){ // 左下标一定小于右下标，否则就越界了 if (left < right) { // 对数组进行分割，取出下次分割的基准标号 int base = division(list, left, right); // 对“基准标号“左侧的一组数值进行递归的切割，以至于将这些数值完整的排序 QuickSort(list, left, base - 1); // 对“基准标号“右侧的一组数值进行递归的切割，以至于将这些数值完整的排序 QuickSort(list, base + 1, right); } } // 简单选择排序 vector<int> SelectSort(vector<int> list){ // 需要遍历获得最小值的次数 // 要注意一点，当要排序 N 个数，已经经过 N-1 次遍历后，已经是有序数列 vector<int> result = list; for (int i = 0; i < result.size(); i++){ // 用来保存最小值得索引 int index = i; // 用来保存最小值得索引 for (int j = i + 1; j < result.size(); j++){ if (result[index] > result[j]){ index = j; } } // 将找到的第i个小的数值放在第i个位置上 swap(result[i], result[index]); cout << "第" << i + 1<< "趟:\t"; for (int i = 0; i < result.size(); i++){ cout << result[i] << " "; } cout << endl; } return result; } // 堆排序的初始化函数 void HeapAdjust(vector<int> &list, int parent, int length){ int temp = list[parent]; // temp保存当前父节点 int child = 2 * parent + 1; // 先获得左孩子 while (child < length){ // 如果有右孩子结点，并且右孩子结点的值大于左孩子结点，则选取右孩子结点 if (child + 1 < length && list[child] < list[child + 1]){ child++; } // 如果有右孩子结点，并且右孩子结点的值大于左孩子结点，则选取右孩子结点 if (temp >= list[child]){ break; } // 把孩子结点的值赋给父结点 list[parent] = list[child]; // 选取孩子结点的左孩子结点,继续向下筛选 parent = child; child = 2 * parent + 1; } list[parent] = temp; } // 堆排序 vector<int> HeadSort(vector<int> list){ int length = list.size(); // 循环建立初始堆 for (int i = length / 2; i >= 0; i--){ HeapAdjust(list, i, length); } // 进行n-1次循环，完成排序 for (int i = length - 1; i > 0; i--){ // 最后一个元素和第一元素进行交换 int temp = list[i]; list[i] = list[0]; list[0] = temp; // 筛选 R[0] 结点，得到i-1个结点的堆 HeapAdjust(list, 0, i); cout << "第" << length - i << "趟排序:"; for (int i = 0; i < list.size(); i++){ cout << list[i] << " "; } cout << endl; } return list; } // 归并排序的合并函数 void Merge(vector<int> &input, int left, int mid, int right, vector<int> temp){ int i = left; // i是第一段序列的下标 int j = mid + 1; // j是第二段序列的下标 int k = 0; // k是临时存放合并序列的下标 // 扫描第一段和第二段序列，直到有一个扫描结束 while (i <= mid && j <= right){ // 判断第一段和第二段取出的数哪个更小，将其存入合并序列，并继续向下扫描 if (input[i] <= input[j]){ temp[k++] = input[i++]; } else{ temp[k++] = input[j++]; } } // 若第一段序列还没扫描完，将其全部复制到合并序列 while (i <= mid){ temp[k++] = input[i++]; } // 若第二段序列还没扫描完，将其全部复制到合并序列 while (j <= right){ temp[k++] = input[j++]; } k = 0; // 将合并序列复制到原始序列中 while (left <= right){ input[left++] = temp[k++]; } } // 归并排序 void MergeSort(vector<int> &input, int left, int right, vector<int> temp){ if (left < right){ int mid = (right + left) >> 1; MergeSort(input, left, mid, temp); MergeSort(input, mid + 1, right, temp); Merge(input, left, mid, right, temp); } } // 归并排序 void mergesort(vector<int> &input){ // 在排序前，先建好一个长度等于原数组长度的临时数组，避免递归中频繁开辟空间 vector<int> temp(input.size()); MergeSort(input, 0, input.size() - 1, temp); } // 基数排序