排序专项整理
2024-06-09 19:13:09
发布于：浙江
排序算法：冒泡排序、选择排序、插入排序、桶排序、归并排序及快速排序
1. 冒泡排序
算法核心思想：两两比较数字，根据升序/降序来判断是否要交换数字。
从第一个数开始判断当前的数和后一个数，是否大/小的数在最右边，不是的话交换两个数的位置。
#include <iostream>
using namespace std;
int a[210];
int main() {
//定义n并且输入n和n个数的数组
int n;
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
//进行冒泡排序，判断当前的数是否比后一个大，如果比后一个大的话交换
for (int i = 1; i <= n - 1; i++) {
for (int j = 1; j <= n - 1; j++) {
if (a[j] > a[j+1]) {
swap(a[j], a[j+1]);
}
}
}
//输出交换后的数组
for (int i = 1; i <= n; i++) {
cout << a[i] << " ";
}
return 0;
}
2. 选择排序
算法核心思想：第一次从所有数字中找到最小(大)值和第一个位置交换，第二个从剩下数字中找到最小(大)值和第二个位置交换，以此类推，直到所有的数字都排序完。
定义一个变量为最小值，假设最小值为第一个，然后将当前变量用for循环的方式与每一个数对比，找出最小
再从剩余未排序元素中继续寻找最小元素，然后放到已排序序列的末尾。
重复第二步，直到所有元素均排序完毕。
#include <iostream>
using namespace std;
int a[1010];
int main() {
////定义n和数组a，并且将n和n个数输入
int n;
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
//定义一个变量为最小值，假设最小值为第一个，然后将当前变量用for循环的方式与每一个数对比，找出最小
for (int i = 1; i <= n-1; i++) {
int k = i; // 最小值的下标
for (int j = i; j <= n; j++) { // 找 a[i]~a[n] 的最小值
if (a[j] < a[k]) {
k = j;
}
}
// 将 a[i]~a[n] 的最小值和 a[i] 交换
swap(a[k], a[i]);
}
//最后输出排序好的数组
for (int i = 1; i <= n; i++) {
cout << a[i] << " ";
}
return 0;
}
3. 插入排序
算法核心思想：
1.从第一个元素开始，该元素可以认为已经被排序；
2.取出下一个元素，在已经排序的元素序列中从后向前扫描；
3.如果该元素（已排序）大于新元素，将该元素移到下一位置；
4.重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；
5.将新元素插入到该位置后;
#include <iostream>
using namespace std;
int a[110];
int main() {
//输入n一个数组
int n;
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
//从第二位开始进行插入排序
for (int i = 2; i <= n; i++) {
//当前需要插入的数为当前的第i个数，从后往前比较
int key = a[i], j = i - 1;
//如果j不小于1，并且前面的数比当前需要插入的数大，那么将前一位的数后移
while (j >= 1 && a[j] > key) {
a[j + 1] = a[j];
j--;
}
//插入当前的数，并且把这一趟插入后的数组输出
a[j + 1] = key;
}
for (int i = 1; i <= n; i++) {
cout << a[i] << " ";
}
return 0;
}
4. 桶排序
算法核心思想：
设计一定数值范围的 "桶"，将属于这个范围的数值按下标，以计数的方式记录到 "桶" 中，然后根据记录的数量，输出多少次即可。
输入n和数组，并且将出现的数用桶标记
遍历数组cnt，注意遍历的范围是数字的范围（例如1~100）
i出现的次数是 a[i],则输出 a[i]个i。
#include <iostream>
using namespace std;
int a[110];
int main() {
//输入n和数组，并且将出现的数用桶标记
int n;
cin >> n;
for (int i = 0; i < n; i++) {
int x;
cin >> x;
a[x]++;
}
//遍历数组cnt，注意遍历的范围是数字的范围（1~100）
for (int i = 1; i <= 100; i++) {
for (int j = 1; j <= a[i]; j++) {
//i出现的次数是 a[i],则输出 a[i]个i
cout << i << " ";
}
}
return 0;
}
5. 归并排序
算法核心思想：
1、定义变量 n 和数组
2、划分，左端点为 1，右端点为 n，递归处理
2.1、递归的结束条件:只有一个数，就不用再递归下去，直接返回
2.2、找到中间位置，递归处理左半部分，递归处理右半部分
3、合并，两个序列分别为[l,mid] 和 [mid+1,r]，从最左边开始，依次比较，小的数放入结果数组temp，下标右移
3.1、判断两个序列是否有剩余，有剩余的，全部放入结果数组 temp
4、把结果数组 temp 重新赋给 a 数组
5、输出a数组
#include<iostream>
using namespace std;
int n , a[1010] , temp[1010];
void MergeSort(int l , int r){
//2.1、递归的结束条件:只有一个数，就不用再递归下去，直接返回
if(l == r)
return;
//2.2、找到中间位置，递归处理左半部分，递归处理右半部分
int mid = (l + r) / 2;
MergeSort(l , mid);
MergeSort(mid + 1 , r);
//3、合并，两个序列分别为[l,mid] 和 [mid+1,r]，从最左边开始，依次比较，小的数放入结果数组temp，下标右移
int i = l, j = mid + 1, k = l;
while(i <=mid && j <= r){
if(a[i] <= a[j])
temp[k++] = a[i++];
else
temp[k++] = a[j++];
}
//3.1、判断两个序列是否有剩余，有剩余的，全部放入结果数组 temp
while(i <= mid)
temp[k++] = a[i++];
while(j <= r)
temp[k++] = a[j++];
//4、把结果数组 temp 重新赋给 a 数组
for(int i = l; i <= r; i++)
a[i] = temp[i];
//5、输出a数组
for(int i = 1; i <= n; i++)
cout << a[i] << " ";
cout << endl;
}
int main(){
//1、定义变量 n 和数组
cin >> n;
for(int i = 1; i <= n; i++)
cin >> a[i];
//2、划分，左端点为 1，右端点为 n，递归处理
MergeSort(1 , n);
return 0;
}
6. 快速排序
算法核心思想：
定义 QuickSort 函数对 a 数组中1~n 的元素进行升序排序，定义 partition 函数 以第一个元素为枢轴进行划分，并返回划分后枢轴的下标位置。
QuickSort 中：当 l>=r 时只有一个元素，不能划分，递归结束。pop 为划分后枢轴的下标位置，等于 partition(a, l, r);，划分结束输出整个 a数组，然后继续对枢轴左边的元素进行划分：QuickSort(a, l, pos - 1);，再对枢轴右边的元素进行划分：QuickSort(a, pos + 1, r);。
partition 中定义 l、r为左右指针，k 为枢轴元素，等于 a[l]，然后利用while 循环将比 k 小的元素放在 k 的左边，比 k 大的元素放在 k 的右边，循环结束返回枢轴的位置 i。
1、定义变量 n 和数组，输入
2、快速排序，递归处理
2.1、结束条件
2.2、找到一趟快速排序后，记录枢轴的位置
2.3、输出一次的结果
2.4、递归处理左右两边
3、找枢轴的位置，保证枢轴左边的都比枢轴小，枢轴右边的都比枢轴大
3.1、l和r分别为左右端点，k为枢轴
3.2、右边的元素比枢轴大，右端点左移
3.3、左边的元素比枢轴小，左端点右移
#include <iostream>
using namespace std;
int a[1005];
int n;
int partition(int a[], int l, int r)
{
//3、找枢轴的位置，保证枢轴左边的都比枢轴小，枢轴右边的都比枢轴大
//3.1、l和r分别为左右端点，k为枢轴
int k = a[l]; //枢轴
while (l < r)
{
//3.2、右边的元素比枢轴大，右端点左移
while (l < r && a[r] >= k)
r--;
a[l] = a[r];
//3.3、左边的元素比枢轴小，左端点右移
while (l < r && a[l] <= k)
l++;
a[r] = a[l];
}
a[l] = k;
return l; //返回枢轴位置
}
//数组 a 的[l,r] 排序(升序）
void QuickSort(int a[], int l, int r)
{
//2.1、结束条件
if (l >= r) return; //只有一个元素，不能划分，返回
//2.2、找到一趟快速排序后，记录枢轴的位置
int pos = partition(a, l, r);//划分后枢轴的位置
//2.3、输出一次的结果
for(int i = 1; i <= n; i++)
cout << a[i] << " ";
cout << endl;
//2.4、递归处理左右两边
QuickSort(a, l, pos - 1);
QuickSort(a, pos + 1, r);
}
int main()
{
//1、定义变量 n 和数组，输入
cin >> n;
for (int i = 1; i <= n; i++)
cin >> a[i];
//2、快速排序，递归处理
QuickSort(a, 1, n);
return 0;
}
6. sort (非常非常非常重要！！！)
格式：sort(开始地址, 结束地址+1, 排序方式);
//升序
#include <iostream>
#include <algorithm>
using namespace std;
int a[110];
int main() {
//输入n并且输入n的数组
int n;
cin >> n;
for (int i = 0; i < n; i++) {
cin >> a[i];
}
//用sort排序完毕后直接输出
sort(a,a + n);
for (int i = 0; i < n; i++) {
cout << a[i] << " ";
}
return 0;
}
//降序
#include <iostream>
#include <algorithm>
using namespace std;
int a[110];
bool cmp(int x, int y){
return x > y;
}
int main() {
//输入n并且输入n的数组
int n;
cin >> n;
for (int i = 0; i < n; i++) {
cin >> a[i];
}
//用sort排序完毕后直接输出
sort(a, a + n, cmp);
for (int i = 0; i < n; i++) {
cout << a[i] << " ";
}
return 0;
}
有帮助，赞一个