c++数组排序，举个例子说明

### C++ 中对数组进行快速排序的实现 快速排序是一种高效的排序算法，其核心思想是分治法。它通过选取一个基准值（pivot），将待排序数组划分为两个子数组，使得左侧子数组中的所有元素均小于等于基准值，右侧子数组中的所有元素均大于基准值。随后递归地对这两个子数组应用相同的操作，直到整个数组有序。 以下是基于 C++ 的快速排序实现： #### 快速排序代码示例 ```cpp #include <iostream> using namespace std; // 交换两个数的辅助函数 void swap(int& a, int& b) { int temp = a; a = b; b = temp; } // 划分函数 int partition(int arr[], int low, int high) { int pivot = arr[high]; // 基准值选为最后一个元素 int i = low - 1; // i 是较小元素索引 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); // 对右半部分递归排序 } } // 主函数测试 int main() { int arr[] = {4, 2, 8, 0, 5, 7, 1, 3, 9}; int n = sizeof(arr) / sizeof(arr[0]); cout << "Original Array: "; for (int i = 0; i < n; i++) cout << arr[i] << " "; cout << endl; quickSort(arr, 0, n - 1); cout << "Sorted Array: "; for (int i = 0; i < n; i++) cout << arr[i] << " "; cout << endl; return 0; } ``` 上述代码实现了经典的快速排序逻辑[^4]。`partition()` 函数负责完成一次划分操作，而 `quickSort()` 函数则递归调用自身来处理左右两部分子数组。 --- #### 使用 STL 提供的 `std::sort` 排序 除了手动编写快速排序外，C++ 标准库提供了更简洁的方式——使用 `<algorithm>` 头文件中的 `std::sort` 函数。该函数底层通常采用混合排序策略（如 IntroSort），性能优异且易于使用。 下面是利用 `std::sort` 对数组进行排序的例子： ```cpp #include <iostream> #include <algorithm> // 引入标准库算法头文件 using namespace std; int main() { int arr[] = {4, 2, 8, 0, 5, 7, 1, 3, 9}; int n = sizeof(arr) / sizeof(arr[0]); cout << "Original Array: "; for (int i = 0; i < n; i++) cout << arr[i] << " "; cout << endl; sort(arr, arr + n); // 调用 std::sort 进行升序排列 cout << "Sorted Array: "; for (int i = 0; i < n; i++) cout << arr[i] << " "; cout << endl; return 0; } ``` 这种方法简单高效，适合大多数场景下的需求[^2]。 --- #### 性能比较 - 手动编写的快速排序具有较高的学习价值，能够帮助理解排序原理。 - `std::sort` 更加通用和优化，在实际开发中推荐优先使用。 ---

### 使用循环实现C++数组排序 在不借助任何内置函数的情况下，可以使用经典的排序算法（如冒泡排序、选择排序或插入排序）仅通过循环来对C++数组进行排序。这些算法完全依赖于嵌套循环和简单的条件判断语句。 #### 冒泡排序 冒泡排序是一种基础的排序方法，其核心思想是比较相邻两个元素大小并交换位置，直到整个序列有序为止。以下是其实现代码： ```cpp #include <iostream> using namespace std; void bubbleSort(int arr[], int n) { for (int i = 0; i < n - 1; ++i) { // 外层控制遍历轮次 bool swapped = false; for (int j = 0; j < n - i - 1; ++j) { // 内层逐一遍历未排序部分 if (arr[j] > arr[j + 1]) { // 如果当前元素大于下一个元素则交换 swap(arr[j], arr[j + 1]); swapped = true; } } if (!swapped) break; // 若某一轮没有发生交换说明已经有序可提前结束 } } int main() { int arr[] = {64, 34, 25, 12, 22, 11, 90}; int n = sizeof(arr)/sizeof(arr[0]); bubbleSort(arr, n); cout << "Sorted array: \n"; for (int i = 0; i < n; ++i) cout << arr[i] << " "; return 0; } ``` 此版本还加入了优化机制：当某一趟扫描中没有任何元素被交换时即可停止后续操作[^1]。 #### 选择排序 选择排序每次从未排序区域找到最小值放到已排序区间的最后面。下面是具体实现过程： ```cpp #include <iostream> using namespace std; void selectionSort(int arr[], int n){ for(int i=0;i<n-1;++i){ // 遍历每一个待选位置 int minIndex=i; for(int j=i+1;j<n;++j){ // 寻找剩余区间内的最小值索引 if(arr[minIndex]>arr[j]){ minIndex=j; } } if(minIndex!=i)// 将发现的新最小值与当前位置互换 swap(arr[minIndex],arr[i]); } } int main(){ int data[]={8,7,6,5,4,3,2,1}; int size=sizeof(data)/sizeof(data[0]); selectionSort(data,size); for(auto elem:data){ cout<<elem<<" "; } return 0; } ``` 这段程序展示了如何利用双重for-loop完成基本的选择排序功能[^2]。 #### 插入排序 插入排序的工作原理类似于整理扑克牌的过程——将新读取的一个记录按关键字大小插到前面适当的位置上去形成新的有序子表。下面给出相应的例子： ```cpp #include<iostream> using namespace std; // Function to perform insertion sort on the given array 'arr' of length 'len' void insertionsort(int arr[], int len){ int key,j; for(int i=1;i<len;i++){ key=arr[i]; j=i-1; /* Move elements of arr[0..i-1], that are greater than key, * to one position ahead of their current position */ while(j>=0 && arr[j]>key){ arr[j+1]=arr[j]; j--; } arr[j+1]=key; } } int main(){ int numbers[]={5,2,-3,10,23,-12}; int count=sizeof(numbers)/sizeof(numbers[0]); insertionsort(numbers,count); for(int k=0;k<count;k++) cout<<numbers[k]<<" "; return 0; } ``` 上述三种都是典型的只依靠循环结构就能达成目的的经典排序技术之一[^3]。 ---