排序
这里有个带图的博客,有助于理解和复习,博客链接
冒泡排序(Bubble Sort)
思路:一共有n个数,那么需要比n-1趟,每一趟比上次都会少比一个数,因为每次都会把最大的数上浮上去(从小到大排)。
时间复杂度: 平均时间复杂度 n2 , 最坏平均时间复杂度 n2 ,最好平均时间复杂度n2(指的是未优化的冒泡排序)。
空间复杂度: O(1) , 因为只需要一个temp变量
稳定性 :是稳定的,因为如果两个值相等,它们之间不需要做交换
//未优化的冒泡排序
#include <iostream>
using namespace std;
const int maxn = 1e5+5;
int arr[maxn];
int main(){
int n;
while(cin>>n){
for(int i = 0; i < n; ++i){
cin>>arr[i];
}
int temp = 0;
for(int i = 0; i < n-1; ++i){
for(int j = 0; j < n-1-i; ++j){
if(arr[j] > arr[j+1]){
temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}
int flag = 1;
for(int i = 0 ; i < n ; ++i){
if(flag){
cout<<arr[i];
flag=0;
} else {
cout<<" "<<arr[i];
}
}
}
return 0;
}
可以做一个简单的优化,每次用isSwap检验这一轮是否发生过交换,如果没有,说明剩下的序列是有序的,不需要再排。这样最好平均时间复杂度是O(n)。
#include <iostream>
using namespace std;
const int maxn = 1e5+5;
int arr[maxn];
int main(){
int n;
while(cin>>n){
for(int i = 0; i < n; ++i){
cin>>arr[i];
}
int temp = 0;
int isSwap = 0;
for(int i = 0; i < n-1; ++i){
isSwap = 0;
for(int j = 0; j < n-1-i; ++j){
if(arr[j] > arr[j+1]){
isSwap = 1;
temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
if(isSwap==0){
break;
}
}
int flag = 1;
for(int i = 0 ; i < n ; ++i){
if(flag){
cout<<arr[i];
flag=0;
} else {
cout<<" "<<arr[i];
}
}
cout<<endl;
}
return 0;
}
选择排序(Selection Sort)
思路: 将序列分为有序区和无序区,每次从无序区中选择一个出来最小的数,放在序列的首部,构成有序区的尾部,直到所有无序区排列完成。
时间复杂度: 平均时间复杂度 n2 , 最坏平均时间复杂度 n2 ,最好平均时间复杂度n2
空间复杂度 O(1)
稳定性 : 不稳定 ,对于序列6 9 6 3 10, 第一遍选择第1个元素6会和3交换,那么原序列中2个6的相对前后顺序就被破坏了,所以选择排序不是一个稳定的排序算法
#include <iostream>
using namespace std;
const int maxn = 1e5+5;
int arr[maxn];
void sort(int *arr ,int len);
int main(){
int n;
while(cin>>n){
for(int i = 0; i < n; ++i){
cin>>arr[i];
}
sort(arr,n);
int flag = 1;
for(int i = 0 ; i < n ; ++i){
if(flag){
cout<<arr[i];
flag=0;
} else {
cout<<" "<<arr[i];
}
}
cout<<endl;
}
return 0;
}
void sort(int *arr ,int len){
int minIndex ;
int temp;
for(int i = 0 ;i< len - 1; ++i){
minIndex = i;
for(int j = i + 1; j < len; ++j){
if(arr[j] < arr[minIndex]){
minIndex = j;
}
}
temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
}
插入排序
思路: 好比打扑克牌的时候,桌子上一堆无序的牌,每次抠出来一张,就插在手上握着的有序的牌,手上的牌是左边的有序区,桌上的牌是右边的无序区。
时间复杂度:平均时间复杂度 n2 , 最坏平均时间复杂度 n2 ,最好平均时间复杂度n
空间复杂度:空间复杂度 O(1)
稳定性 : 稳定 ,可以让后面的数不插在相等的数前面
#include <iostream>
using namespace std;
const int maxn = 1e5+5;
int arr[maxn];
void sort(int *arr ,int len);
int main(){
int n;
while(cin>>n){
for(int i = 0; i < n; ++i){
cin>>arr[i];
}
sort(arr,n);
int flag = 1;
for(int i = 0 ; i < n ; ++i){
if(flag){
cout<<arr[i];
flag=0;
} else {
cout<<" "<<arr[i];
}
}
cout<<endl;
}
return 0;
}
void sort(int *arr ,int len){
int preIndex ,current;
for(int i=1;i<len;++i){
current = arr[i];
preIndex = i-1;
while(preIndex>=0 && arr[preIndex] > current){
arr[preIndex+1] = arr[preIndex];
preIndex--;
}
arr[preIndex+1] = current;
}
}
快速排序
思路: 对于每个要排列的区间,选择第一个数或者最后一个数作为基准,将该区间的数,分为两部分左边的小于基准,右边的大于基准,两个指针移动的过程中,关键在于最后i==j的位置就是基准插入的地方。
关于分析快速排序的时间的复杂度,和BST类似,想成一个二叉搜索树,最糟糕的情况就是一字长蛇阵,最好的情况就是类似于满二叉树,对于每一层都要做n次比较,而树的深度可以为n ,也可以为log2n,所以...
时间复杂度 : 平均时间复杂度 nlog2n , 最坏平均时间复杂度 n2 ,最好平均时间复杂度nlog2n
空间复杂度 : 最好是log2n 最坏是n
稳定性: 不稳定,不稳定发生在基准和其他元素交换的时刻
#include <iostream>
using namespace std;
const int maxn = 1e5+5;
int arr[maxn];
void quickSort(int *arr ,int s ,int t);
int main(){
int n;
while(cin>>n){
for(int i = 0; i < n; ++i){
cin>>arr[i];
}
quickSort(arr,0,n-1);
int flag = 1;
for(int i = 0 ; i < n ; ++i){
if(flag){
cout<<arr[i];
flag=0;
} else {
cout<<" "<<arr[i];
}
}
cout<<endl;
}
return 0;
}
void quickSort(int *arr ,int s ,int t){
int i = s;
int j = t;
int temp ;
if(s<t){
temp = arr[s];
while(i!=j){
while(j>i && arr[j] >= temp ) j--;
arr[i] = arr[j];
while(j>i && arr[i] <= temp ) i++;
arr[j] = arr[i];
}
arr[i] = temp ;
quickSort(arr,s,i-1);
quickSort(arr,i+1,t);
}
}
堆排序
时间复杂度 : 最好最坏是nlog2n
空间复杂度 : O(1)
稳定性: 不稳定
#include <iostream>
using namespace std;
const int maxn = 1e5+5;
int tree[maxn];
int parent(int i){
return i/2;
}
int left(int i){
return i*2;
}
int right(int i){
return i*2+1;
}
void swap(int tree[],int i,int j){
int temp = tree[i];
tree[i] = tree[j];
tree[j] = temp;
}
void max_heapify(int tree[] , int n , int i){
int l = left(i);
int r = right(i);
int largest = i;
if(l <= n && tree[l] > tree[i]){
largest = l;
}
if(r <= n && tree[r] > tree[largest]){
largest = r;
}
if(largest != i){
swap(tree,i,largest);
max_heapify(tree , n , largest);
}
}
void build_heap(int tree[] ,int n){
int last_node = n ;
for(int i = last_node / 2; i>=1 ;--i){
max_heapify(tree, n, i);
}
}
void heap_sort(int tree[] ,int n) {
build_heap(tree,n);
int i;
for(i = n; i >= 1; --i) {
swap(tree,i,1);
max_heapify(tree, i-1, 1);
}
}
int main(){
int n;
cin>>n;
for(int i=1 ; i <= n ; ++i){
cin>>tree[i];
}
heap_sort(tree,n);
int i;
for(i = 1;i <= n; ++i){
cout<<tree[i]<<endl;
}
return 0;
}