C++算法之数据排序

算法之数据排序"/>

C++算法之数据排序

获取信息后会进行处理，以便于利用，而排序是处理的一种。以下介绍数据排序的几种常用方法。

---

目录

1.选择排序

1.1 基本思想

1.2.排序过程

 1.3 具体代码

2.冒泡排序 

2.1 基本思想

2.2 排序过程

 2.3 具体代码

3.插入排序 

3.1 基本思想

3.2 排序过程

​编辑 3.3 具体代码 

4.桶排序

4.1 基本思想

4.2 排序过程

4.3 具体代码                                        

5.快速排序

5.1 基本思想

5.2 排序过程

 5.3 具体代码

6.归并排序

6.1 基本思想

6.2 排序过程

6.3 具体代码

7.总结

7.1 稳定性

7.2 时间复杂性

---

1.选择排序

1.1 基本思想

每一趟都从待排序的元素中找出最小或最大的一个元素，把它放在待排序数列的最前面，直到所有元素排序完。

1.2.排序过程

 1.3 具体代码

#include <bits/stdc++.h>
using namespace std;
int a[10000005];
int main()
{int n;cin>>n;for(int i=1; i<=n; i++) //输入cin>>a[i];for(int i=1; i<n; i++){int min = i;for(int j= i+1 ; j<= n ; j++)if(a[j]<a[min]) //找出最小值min = j;swap( a[i] , a[min] ); //交换位置}for(int i=1; i<=n; i++) //输出cout<<a[i]<<" ";return 0;
}

2.冒泡排序 

2.1 基本思想

如有n个数字，则进行n-1轮比较，每一轮都从第一个开始，依次比较相邻的两个数是否逆序，如果逆序就互相交换，直到最后一个数字。

2.2 排序过程

 2.3 具体代码

#include <bits/stdc++.h>
using namespace std;
int main() {   int n,a[100005];cin >> n;for(int e = 1;e <= n;e++)cin >> a[e]; //输入for (int i = 1; i < n; ++i) {  // 将序列从1到n-i+1的最大值，移到n-i+1的位置for (int j = 1; j <= n - i; ++j)// 其中j枚举的是前后交换元素的前一个元素序号if (a[j] > a[j + 1]) swap(a[j], a[j + 1]);}for (int i = 1; i <= n; ++i)cout << a[i] << ' '; //输出cout << endl;return 0;
}

3.插入排序 

3.1 基本思想

当输入一个元素时，在已经排序好的数列中寻找它应该在的位置，然后把它后面的所有元素后移一位，再把它放入。

3.2 排序过程

 3.3 具体代码 

#include<bits/stdc++.h>
using namespace std;
int main() {int l,a[100005];int temp, i, j;cin >> l;for(int e = 0;e < l;e++)cin >> a[e];for (i = 1; i < l; i++) {  // 数组的下标是从0开始的// 这里从第二个数开始枚举  即假定第一个数是有序的temp = a[i]; j = i;     // 这里temp 临时储存每一次需要排序的数while (j >= 1 && temp < a[j - 1]) {a[j] = a[j - 1];j--;}a[j] = temp;}for (i = 0; i < l; i++) {cout << a[i] << " ";}cout << endl;return 0;
}

4.桶排序

4.1 基本思想

如果待排序的数列值在一个有限范围内时，可以设计有限个有序桶，将待排序的数值放入对应的桶里，桶号就是待排序的数值。然后输出各桶的值，就得到一个有序的数列了。

4.2 排序过程

4.3 具体代码                                        

#include <bits/stdc++.h>
using namespace std;
int main()
{int book[1001],i,j,n,k;cin>>n;  //输入个数for(i=0;i<=1000;i++)  //创造1000个桶，默认里面都装0个 {book[i]=0;}for(i=0;i<n;i++)   //输入数字，向对应数字的桶里放数字 {cin>>k; book[k]++;    }for(i=1;i<1000;i++) //输出结果{for(j=1;j<=book[i];j++){cout<<i<<" "; //检验每个箱子里的个数，0的直接舍弃掉 }}return 0;
} 

5.快速排序

5.1 基本思想

快速排序是对冒泡排序的改进。它通过一趟排序将待排序记录分为2部分，一部分的关键字都比另一部分的关键字小，然后分别对它们进行排序，直到都有序。

5.2 排序过程

 5.3 具体代码

#include <bits/stdc++.h>
#define N 100010 
using namespace std; 
int n; 
int a[N]; void quick_sort(int l, int r) { // 设置最右边的数为分界线int pivot = a[r];// 元素移动int k = l - 1;for (int j = l; j < r; ++j)if (a[j] < pivot) swap(a[j], a[++k]); swap(a[r], a[++k]); if (l < k - 1) quick_sort(l, k - 1); // 如果序列的分界线左边的子段长度>1，排序if (k + 1 < r) quick_sort(k + 1, r); // 如果序列的分界线右边的子段长度>1，排序// 上面的过程结束后，到这里左子段和右子段已经分别排好序。又因为确定分界线以后的移动操作// 保证了左子段中的元素都小于等于分界线，右子段中的元素都大于分界线。所以整个序列也是有序的。
} int main() { // 输入scanf("%d", &n); for (int i = 1; i <= n; ++i) scanf("%d", &a[i]); // 快速排序quick_sort(1, n); // 输出for (int i = 1; i <= n; ++i) printf("%d ", a[i]);  return 0; 
} 

6.归并排序

6.1 基本思想

这是采用分治法（Divide and Conquer）的典型应用。先使每个子序列有序，再把已经有序的子序列合并，得到完全有序的序列。归并发主要分为分解、合并两步。

6.2 排序过程

6.3 具体代码

#include<bits/stdc++.h>
using namespace std;
void mergearray(int a[],int first,int mid,int last,int temp[])	//将两个有序数组合并排序 
{int i=first,j=mid+1;int m=mid,n=last;int k=0;while(i<=m&&j<=n){if(a[i]<a[j])temp[k++]=a[i++];elsetemp[k++]=a[j++];}while(i<=m)temp[k++]=a[i++];while(j<=n)temp[k++]=a[j++];for(i=0;i<k;i++)a[first+i]=temp[i];
}void mergesort(int a[],int first,int last,int temp[])	//将两个任意数组合并排序 
{if(first<last){int mid=(first+last)/2;mergesort(a,first,mid,temp);	//左边有序 mergesort(a,mid+1,last,temp);	//右边有序 mergearray(a,first,mid,last,temp);	//再将两个有序数组合并 }
}int main()
{int a[1005];int temp[1005];int n;scanf("%d",&n);for(int i=0;i<n;i++)scanf("%d",&a[i]);mergesort(a,0,n-1,temp);for(int i=0;i<n;i++)printf("%d ",a[i]);
}

7.总结

7.1 稳定性

插入排序、冒泡排序、归并排序等线性排序是稳定的。

选择排序、快速排序等有跨度的排序是不稳定的。

7.2 时间复杂性

插入排序、冒泡排序、选择排序的时间复杂性是O（）。

快速排序、归并排序的时间复杂性是O（ n）。

桶排序的时间复杂性是O（n）。

---

创作不易，白嫖不好，各位的支持和认可，就是我创作的最大动力，如果喜欢我的文章，给个关注吧！

冰焰狼 | 文

如果本篇博客有任何错误，请批评指教，不胜感激 ！