#include <cmath>
#include <iostream>
#include <algorithm>
using namespace std;
int test[100] = {3,5,7,1,19,0,21,5,36,14};
int base[100] = {3,5,7,1,19,0,21,5,36,14}; // 比较用
int len = 10;
void print(int *a, int l){
for(int i = 0; i < l; ++i)cout<<a[i]<<' ';
cout<<endl;
}
//直接选择
void directInsertSort(int *a, int l){
int count = 0;
for(int i = 0; i < l; ++i){
int tmp = a[i];
for(int j = i-1; j>=0; --j){
if(a[j]>tmp && ++count){
swap(a[j+1],a[j]);
}else{
break;
}
}
}
cout<<count<<':';
print(test,len);
}
//希尔排序
void shellSort(int *a, int l){
int count = 0;
for(int step = l/2; step>0; step /=2){
for(int i = 0; i < l; ++i){
int tmp = a[i];
for(int j = i-step; j >= 0; j-=step){
if(a[j]>tmp && ++count)
swap(a[j+step],a[j]);
else1
break;
}
}
}
cout<<count<<':';
print(test,len);
}
//堆排序
int cnt_for_heap = 0;
void percolateDown(int *a, int p, int l){
int pointer = p;
while(pointer<(l/2-1)){
if(a[pointer]>a[(pointer+1)*2-1] && a[pointer]>a[(pointer+1)*2])break;
else{
++cnt_for_heap;
if(a[(pointer+1)*2-1]>a[(pointer+1)*2]){
swap(a[pointer],a[(pointer+1)*2-1]);
pointer = (pointer+1)*2-1;
}else{
swap(a[pointer],a[(pointer+1)*2]);
pointer = (pointer+1)*2;
}
}
}
if((pointer+1)*2 ==l && a[(pointer+1)*2-1]>a[pointer]) swap(a[pointer],a[(pointer+1)*2-1]);
}
void buildHeap(int *a, int l){
for(int i = l/2-1;i>=0;--i)
percolateDown(a,i,l);
}
void heapSort(int *a, int l){
cnt_for_heap = 0;
buildHeap(a,l);
for(int i = l-1; i >= 0; --i){
swap(a[0],a[i]);++cnt_for_heap;
percolateDown(a,0,i);
}
cout<<cnt_for_heap<<":";
print(a,l);
}
//冒泡排序
void bubbleSort(int *a, int l){
int count = 0;
for(int i = l-1; i >= 0; --i){
bool flag = 0;
for(int j = i-1; j >=0; --j){
if(a[j+1]<a[j]){
++count;
swap(a[j],a[j+1]);
flag = 1;
}
}
if(!flag)break;
}
cout<<count<<':';
print(a,l);
}
// 快速排序
int cnt_for_quick = 0;
int divide(int *a, int l, int h){
int k = a[l];
do{
while(l<h && a[h] >= k)--h;
if(l<h)a[l++] = a[h],
++cnt_for_quick;
while(l<h && a[l] <= k)++l;
if(l<h)a[h--] = a[l],
++cnt_for_quick;
}while(l<h);
a[l] = k;
return l;
}
void quick(int *a, int l, int h){
if(l>=h)return;
int mid = divide(a,l,h);
quick(a,l,mid-1);
quick(a,mid+1,h);
}
void quickSort(int *a, int l){
cnt_for_quick = 0;
quick(a,0,l-1);
cout<<cnt_for_quick<<':';
print(a,l);
}
//归并排序
int cnt_for_merge = 0;
void merge(int *a, int l, int mid, int r){
int i = l, j = mid, k = 0;
int *tmp = new int[r-l+1];
while(i<mid && j <= r){
if(a[i]<a[j])tmp[k++]-+ = a[i++];
else tmp[k++] = a[j++];
++cnt_for_merge;
}
while(i<mid)tmp[k++] = a[i++],++cnt_for_merge;
while(j<=r)tmp[k++] = a[j++],++cnt_for_merge;
for(i = l, k = 0; i <= r;)
a[i++] = tmp[k++];
delete [] tmp;
}
void mergeS(int *a, int l, int h){
int mid = (l+h)/2;
if(l==h)return ;
mergeS(a,l,mid);
mergeS(a,mid+1,h);
merge(a,l,mid+1,h);
}
void mergeSort(int *a, int l){
cnt_for_merge = 0;
mergeS(a,0,l-1);
cout<<cnt_for_merge<<':';
print(a,l);
}
int main(){
print(test,len);
mergeSort(test,len);
sort(base,base+len);
print(base,len);
}
转载请注明原文地址: https://www.6miu.com/read-44080.html
