C++实现常见排序算法详解与代码示例

资源摘要信息:"cpp代码-常见排序算法" 在信息技术领域，排序算法是基础且极为重要的算法之一。它用于将一系列数据按照一定的顺序（通常是从小到大或从大到小）进行排列。掌握多种排序算法对于编写高效、稳定的程序至关重要。下面将介绍一些常见的排序算法，并以C++代码形式体现。 1. 冒泡排序（Bubble Sort） 冒泡排序是最简单的排序算法之一。它通过重复遍历待排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。遍历数列的工作是重复进行直到没有再需要交换，也就是说该数列已经排序完成。 冒泡排序的平均和最坏情况时间复杂度均为O(n^2)，它对n个项目需要O(n^2)的比较次数，且可以就地排序。 C++代码示例： ```cpp void bubbleSort(int arr[], int n) { for (int i = 0; i < n-1; i++) for (int j = 0; j < n-i-1; j++) if (arr[j] > arr[j+1]) swap(arr[j], arr[j+1]); } ``` 2. 选择排序（Selection Sort） 选择排序算法是通过重复遍历待排序的数列，选择最小（或最大）的元素，并将其放置在序列的起始位置。对于剩余的元素，重复这个过程，每次迭代选择下一个最小（或最大）的元素并将其放置在适当的位置。 选择排序的时间复杂度为O(n^2)，但它在处理大量元素时仍能保持较好的性能。 C++代码示例： ```cpp void selectionSort(int arr[], int n) { int i, j, min_idx; for (i = 0; i < n-1; i++) { min_idx = i; for (j = i+1; j < n; j++) if (arr[j] < arr[min_idx]) min_idx = j; swap(arr[min_idx], arr[i]); } } ``` 3. 插入排序（Insertion Sort） 插入排序的工作方式类似于我们手头排序扑克牌。从第二个元素开始，将每个新元素插入其已排序序列的适当位置。它通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。 插入排序在最好的情况下的时间复杂度为O(n)，当输入序列已经部分排序时效率很高。 C++代码示例： ```cpp void insertionSort(int arr[], int n) { int key, j; for (int i = 1; i < n; i++) { key = arr[i]; j = i - 1; while (j >= 0 && arr[j] > key) { arr[j + 1] = arr[j]; j = j - 1; } arr[j + 1] = key; } } ``` 4. 希尔排序（Shell Sort） 希尔排序是基于插入排序的算法。它首先会将待排序的记录分割成若干子序列，然后分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行一次直接插入排序。 希尔排序的时间复杂度依赖于间隔序列的选取，一般情况下，希尔排序的时间复杂度介于O(n)和O(n^2)之间。 C++代码示例： ```cpp void shellSort(int arr[], int n) { for (int gap = n/2; gap > 0; gap /= 2) { for (int i = gap; i < n; i++) { int temp = arr[i]; int j; for (j = i; j >= gap && arr[j - gap] > temp; j -= gap) arr[j] = arr[j - gap]; arr[j] = temp; } } } ``` 5. 归并排序（Merge Sort） 归并排序是一种分治算法，其思想是将原始数组切分成更小的数组，直到每个小数组只有一个位置，然后将小数组归并成较大的数组，直到最后只有一个排序完毕的大数组。 归并排序的时间复杂度为O(n log n)，是一种效率比较高的排序算法。 C++代码示例： ```cpp void merge(int arr[], int l, int m, int r) { int i, j, k; int n1 = m - l + 1; int n2 = r - m; int L[n1], R[n2]; for (i = 0; i < n1; i++) L[i] = arr[l + i]; for (j = 0; j < n2; j++) R[j] = arr[m + 1 + j]; i = 0; j = 0; k = l; while (i < n1 && j < n2) { if (L[i] <= R[j]) { arr[k] = L[i]; i++; } else { arr[k] = R[j]; j++; } k++; } while (i < n1) { arr[k] = L[i]; i++; k++; } while (j < n2) { arr[k] = R[j]; j++; k++; } } void mergeSort(int arr[], int l, int r) { if (l < r) { int m = l + (r - l) / 2; mergeSort(arr, l, m); mergeSort(arr, m + 1, r); merge(arr, l, m, r); } } ``` 6. 快速排序（Quick Sort） 快速排序也是一种分治算法，通过选择一个“基准”元素，重新排序数列，所有比基准值小的元素摆放在基准前面，所有比基准值大的元素摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。 快速排序的时间复杂度在平均情况下为O(n log n)，但最坏情况下退化到O(n^2)。 C++代码示例： ```cpp int partition(int arr[], int low, int high) { int pivot = arr[high]; int i = (low - 1); for (int j = low; j <= high- 1; j++) { if (arr[j] < pivot) { i++; swap(arr[i], arr[j]); } } swap(arr[i + 1], arr[high]); return (i + 1); } void quickSort(int arr[], int low, int high) { if (low < high) { int pi = partition(arr, low, high); quickSort(arr, low, pi - 1); quickSort(arr, pi + 1, high); } } ``` 7. 堆排序（Heap Sort） 堆排序是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子节点的键值或索引总是小于（或者大于）它的父节点。 C++代码示例： ```cpp void heapify(int arr[], int n, int i) { int largest = i; int l = 2 * i + 1; int r = 2 * i + 2; if (l < n && arr[l] > arr[largest]) largest = l; if (r < n && arr[r] > arr[largest]) largest = r; if (largest != i) { swap(arr[i], arr[largest]); heapify(arr, n, largest); } } void heapSort(int arr[], int n) { for (int i = n / 2 - 1; i >= 0; i--) heapify(arr, n, i); for (int i = n - 1; i > 0; i--) { swap(arr[0], arr[i]); heapify(arr, i, 0); } } ``` 8. 计数排序（Counting Sort） 计数排序不是比较排序，它的运作方式是利用数组下标来确定元素的正确位置。当输入的元素是 n 个 0 到 k 之间的整数时，它的运行时间是 O(n + k)。 计数排序是一个非比较的排序算法，它的优势在于在对一定范围内的整数排序时，它的复杂度为O(n+k)（k是整数的范围），效率高过任何比较排序算法。 C++代码示例： ```cpp void countingSort(int arr[], int n) { int max = arr[0]; for (int i = 1; i < n; i++) if (arr[i] > max) max = arr[i]; int m = max + 1; std::vector<int> count(m); for (int i = 0; i < n; i++) count[arr[i]]++; int index = 0; for (int i = 0; i < m; i++) while (count[i]-- > 0) arr[index++] = i; } ``` 在实际应用中，应根据具体需求和数据特点选择合适的排序算法。例如，对于小规模数据，插入排序和冒泡排序可能表现得相当不错，而对于大规模数据且要求效率较高的情况，应考虑使用归并排序或堆排序等。