排序算法总结(c++)
2022-9-11 更新
选择排序
选择排序的基本思想是:如果有N个元素需要排序 ,那么首先从N个元素中找到最小的那个元素与第0位置上的元素交换 (说明一点,如果没有比原本在第0位置上的元素小的就不用交换了,后面的同样是) ,然后再从剩下的N-1个元素中找到最小的元素与第1位置上的元素交换, 之后再从剩下的N-2个元素中找到最小的元素与第2位置上的元素交换,....... 直到所有元素都排序好 (也就是直到从剩下的2个元素中找到最小的元素与第N-2位置上的元素交换)。
稳定排序的意思是:比如原本一组无序的元素中出现两个相同的值,那么经过稳定排序后这两个相等的元素必然相邻,不改变原来无序状态下的先后顺序叫稳定的排序。
代码
for (int i = 0; i < len - 1; i++) {
int min = i;
int j = i + 1;
for (; j < len; j++){
if (a[min] > a[j])
{
min = j;
}
}
int t = a[i];
a[i] = a[min];
a[min] = t;
}
冒泡排序
1) 从前往后,每相邻的两个元素进行比较,将较大的元素依次往后排;
2) 第一次进行两两元素比较,将最大元素将排在后面,也就是最大索引值处;
3)在第二次进行两两元素比较时,因为已经出现一个最大值,此最大值不参与比较;
4)依次进行比较,当进行第n次比较,有数组长度-1个元素不参与比较,直至所有元素从小到大依次排序.
代码
void bubble(int arr[], int n) {
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n - i - 1; ++j) {
if (arr[j] > arr[j + 1]) {
swap(arr[j], arr[j + 1]);
}
}
}
}
插入排序
把n个待排序的元素看成为一个有序表和一个无序表。开始时有序表中只包含1个元素,无序表中包含有n-1个元素,排序过程中每次从无序表中取出第一个元素,将它插入到有序表中的适当位置,使之成为新的有序表,重复n-1次可完成排序过程。
原理:从待排序的数中选出一个来,插入到前面的合适位置。
代码
//把第一个元素当成有序,从第二个开始,将每个元素跟前面的有序元素比较,插入到合适位置
void insertSort(int a[], int length)
{
for (int i = 1;i < length;i++) {
int temp = a[i]; //取出一个无序元素,该无序元素的前面所有元素已有序
int j = i - 1; //从这个无序元素的前一个元素开始从后往前依次比较
for ( ; j >= 0;j--) {
//如果待插入的元素比当前比较的元素小,则该比较的元素后移
if (temp < a[j]) {
a[j + 1] = a[j];
}
else //如果待插入的元素和当前比较的元素相等或者比它大,则插到这个元素后面
{
break;
}
}
//如果待插入的元素所有元素小,插到最前面
a[j + 1] = temp;
}
}
希尔排序
希尔排序的基本思想是先将整个待排记录序列分割成为若干子序列分别进行直接插入排序,待整个序列中的记录“基本有序”时,再对全体记录进行一次直接插人排序。
一般情况下,先选定step=length/2作为第一增量,然后将距离为step的所有元素分到一组,并对每一组的元素进行直接插入排序。然后再取step/2作为第二增量,重复上述操作。
当增量step减到1时,整个序列被分到一组,然后进行一次直接插入排序,至此希尔排序结束希尔排序的一个特点是:子序列的构成不是简单的“逐段分割”,而是将相隔某个“增量”的记录组成一个子序列。
代码
void ShellSort(int array[],int length){
for(int step=length/2;step>0;step=step/2){//初始步长step为length/2
for(int i=0;i<step;i++){ //遍历每一次分组后的第一个元素
for(int j=i+step;j<length;j+=step){ //遍历步长为step的所有元素 ,进行直接插入排序
int temp=array[j];
int m=j-step;
for(m=j-step;m>=0&&array[m]>temp;m-=step){//array[m]小于 temp 时循环结束,结束后应将 temp 赋值给a[m+step]
array[m+step]=array[m]; //只要array[m]比temp大,就将此数后移一位(此处是step位)
}
array[m+step]=temp; //将 temp 赋值给a[m+step]
}
}
计数排序
计数排序是一种非比较式排序,其基本思想是以空间换时间,其对特定序列的排序时间复杂度为o(n),快于任何传统的比较式排序;
计数排序的核心在于将数值转化为键,存储在额外开辟的数组空间中。作为一种线性时间复杂度的排序,计数排序要求输入的数据必须是有确定范围的整数,其适用场景为:重复数较多的、在一定范围内的整数数列;
步骤
- 1 获取待排序列最大元素的值(imax),申请一个大小为(imax+1)的临时数组(tmp);
- 2 定义变量 i ,从0循环到 imax ,统计待排序列中每个值为 i 的元素出现的次数,记入数组(tmp)的第 i 项中;
- 3 反向填充原数组:将(tmp)中的每个元素按从低到高的顺序放回原序列中。
代码
//计数排序
void count_sort(int *A, int n){
int imax = Aimax(A, n); //获取待排序数组的最大元素的值imax
vector<int>tmp(imax+1); //申请一个临时数组,大小为imax+1
for (int i = 0; i < n; i++) //临时数组计数:计算这个数字的出现频率
tmp[A[i]]++;
int i = 0;
for (int j = 0; j < imax + 1; j++) { //将tmp中的每个元素从低到高顺序放回原数组中
for (int k = 0; k < tmp[j]; k++)
A[i++] = j;
}
}
int Aimax(int *A, int n) { //找数组最大值函数
int imax = 0;
for (int i = 0; i < n; i++) {
imax = imax > A[i] ? imax : A[i];
}
return imax;
}
桶排序
桶排序的基本思想是假设数据在[min,max]之间均匀分布,其中min、max分别指数据中的最小值和最大值。那么将区间[min,max]等分成n份,这n个区间便称为n个桶。将数据加入对应的桶中,然后每个桶内单独排序。由于桶之间有大小关系,因此可以从大到小(或从小到大)将桶中元素放入到数组中。
代码
int* sort_array(int *arr, int n) {
int i;
int maxValue = arr[0];
for (i = 1; i < n; i++)
if (arr[i] > maxValue) // 输入数据的最大值
maxValue = arr[i];
// 设置10个桶,依次0,1,,,9
const int bucketCnt = 10;
vector<int> buckets[bucketCnt];
// 桶的大小bucketSize根据数组最大值确定:比如最大值99, 桶大小10
// 最大值999,桶大小100
// 根据最高位数字映射到相应的桶,映射函数为 arr[i]/bucketSize
int bucketSize = 1;
while (maxValue) { //求最大尺寸
maxValue /= 10;
bucketSize *= 10;
}
bucketSize /= 10; //桶的个数
// 入桶
for (int i=0; i<n; i++) {
int idx = arr[i]/bucketSize; //放入对应的桶
buckets[idx].push_back(arr[i]);
// 对该桶使用插入排序(因为数据过少,插入排序即可),维持该桶的有序性
for (int j=int(buckets[idx].size())-1; j>0; j--) {
if (buckets[idx][j]<buckets[idx][j-1]) {
swap(buckets[idx][j], buckets[idx][j-1]);
}
}
}
// 顺序访问桶,得到有序数组
for (int i=0, k=0; i<bucketCnt; i++) {
for (int j=0; j<int(buckets[i].size()); j++) {
arr[k++] = buckets[i][j];
}
}
return arr;
快排
代码
void quick_sort(int q[], int l, int r)
{
if (l >= r) return;
int i = l - 1, j = r + 1, x = q[l + r >> 1];
while (i < j)
{
do i ++ ; while (q[i] < x);
do j -- ; while (q[j] > x);
if (i < j) swap(q[i], q[j]);
}
quick_sort(q, l, j), quick_sort(q, j + 1, r);
}
归并排序
代码
void merge_sort(int q[], int l, int r)
{
if (l >= r) return;
int mid = l + r >> 1;
merge_sort(q, l, mid);
merge_sort(q, mid + 1, r);
int k = 0, i = l, j = mid + 1;
while (i <= mid && j <= r)
if (q[i] <= q[j]) tmp[k ++ ] = q[i ++ ];
else tmp[k ++ ] = q[j ++ ];
while (i <= mid) tmp[k ++ ] = q[i ++ ];
while (j <= r) tmp[k ++ ] = q[j ++ ];
for (i = l, j = 0; i <= r; i ++, j ++ ) q[i] = tmp[j];
}
桶排序
代码
stl堆
#include <bits/stdc++.h>
using namespace std;
int n,m,x;
priority_queue<int,vector<int>,greater<int> >q;
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
scanf("%d",&x);
q.push(x);
}
for(int i=1;i<=m;i++)
{
printf("%d ",q.top());
q.pop();
}
return 0;
}
复制的
手写堆
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 100010;
int n, m;
int h[N], cnt;
void down(int u)
{
int t = u;
if (u * 2 <= cnt && h[u * 2] < h[t]) t = u * 2;
if (u * 2 + 1 <= cnt && h[u * 2 + 1] < h[t]) t = u * 2 + 1;
if (u != t)
{
swap(h[u], h[t]);
down(t);
}
}
int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i ++ ) scanf("%d", &h[i]);
cnt = n;
for (int i = n / 2; i; i -- ) down(i);
while (m -- )
{
printf("%d ", h[1]);
h[1] = h[cnt -- ];
down(1);
}
puts("");
return 0;
}
时间复杂度
附
总结哈 主要是代码 简单写写 方便复习
看y总算法基础课没讲这些 补充下