排序算法合集
1.插入排序
? ? ? ? 1.步骤
????????????????1.从第一个元素开始,该元素可以认为已经被排序
????????????????2.取下一个元素tem,从已排序的元素序列从后往前扫描
????????????????3.如果该元素大于tem,则将该元素移到下一位
????????????????4.重复步骤3,直到找到已排序元素中小于等于tem的元素
????????????????5.tem插入到该元素的后面,如果已排序所有元素都大于tem,则将tem插入到下标为0的位置
????????????????6.重复步骤2~5。
? ? ? ? 2.动图
? ? ? ? ? ? ? ??
????????3.思路
????????????????? ?在待排序的元素中,假设前n-1个元素已有序,
????????????????? ?现将第n个元素插入到前面已经排好的序列中,使得前n个元素有序。
????????????????? ?按照此法对所有元素进行插入,直到整个序列有序。
????????4.时间复杂度:? ??
????????????????? 最坏情况下为O(N^2)
????????????????? 最好情况下为O(N),此时待排序列为升序,或者说接近升序。
????????5.代码:
#include<bits/stdc++.h>
using namespace std;
void InsertSort(int *arr, int n) {
for (int i = 2; i <= n ; ++i) {
int end = i;
while (end > 1) {
if (arr[end] < arr[end-1]) {
swap(arr[end],arr[end-1]);
end--;
} else {
break;
}
}
}
}
main() {
int a[100],b,c;
cin>>b;
for(int i=1; i<=b; i++) {
cin>>a[i];
}
InsertSort(a,b);
for(int i=1; i<=b; i++) {
cout<<a[i]<<" ";
}
}
2.选择排序
????????1.思路:??
每次从待排序列中选出一个最小值,然后放在序列的起始位置,直到全部待排数据排完即可。
实际上,我们可以一趟选出两个值,一个最大值一个最小值,然后将其放在序列开头和末尾,这样可以使选择排序的效率快一倍。
? ? ? ? 2.动图
????????3.?时间复杂度:
????????????????最坏情况:O(N^2)
?????????? 最好情况:O(N)
?
????????4.代码
#include<bits/stdc++.h>
using namespace std;
void SelectSort(int *arr, int n) {
int begin = 1, end = n ;
while (begin < end) {
int maxi = begin;
int mini = begin;
for (int i = begin; i <= end; ++i) {
if (arr[i] < arr[mini]) {
mini = i;
}
if (arr[i] > arr[maxi]) {
maxi = i;
}
}
swap(arr[mini], arr[begin]);
if (begin == maxi) {
maxi = mini;
}
swap(arr[maxi], arr[end]);
++begin;
--end;
}
}
main() {
int a[100],b;
cin>>b;
for(int i=1; i<=b; i++) {
cin>>a[i];
}
SelectSort(a,b);
for(int i=1; i<=b; i++) {
cout<<a[i]<<" ";
}
}
3.快速排序(我习惯叫“挖坑法”)
? ? ? ? 1.思路
????????????????1.选出一个数据(一般是最左边或是最右边的)存放在key变量中,在该数据位置形成一个坑
????????????????2、定义一个L和一个R,L从左向右走,R从右向左走。(若在最左边挖坑,则需要R先走;若在最右边挖坑,则需要L先走)
? ? ? ? 2.动图
????????
????????3.代码?
#include <iostream>
using namespace std;
void QuickSort(int *array, int low, int high) {
if (low >= high) {
return ;
}
int i = low;
int j = high;
int key = array[low];
while (i < j) {
while (array[j] >= key && i < j) {
j--;
}
array[i] = array[j];
while (array[i] <= key && i < j) {
i++; //找不到则i加一
}
array[j] = array[i];
}
array[i] = key;
QuickSort(array, low, i - 1);
QuickSort(array, i + 1, high);
}
int main() {
int array[10000], abb;
cin >> abb;
for (int i = 1; i <= abb; i++) {
cin >> array[i];
}
cout << "原始序列:";
for (int i = 1; i <= abb; i++) {
cout << array[i] << " ";
}
cout << endl;
QuickSort(array, 1, abb);
cout << "快排序列:";
for (int i = 1; i <= abb; i++) {
cout << array[i] << " ";
}
return 0;
}
????????4.视频????????
全网最清晰快速排序,看完快排思想和代码全部通透,不通透你打我!
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!