6_排序算法_冒泡_选择_插入_快速

1.排序方法：
比较排序：冒泡排序，选择排序，插入排序，快速排序
不用比较的排序：希尔排序，堆排序

冒泡选择插入复杂度是一个级别的O(N^2)
快速堆归并排序是O(NlogN) 希尔是O(N^1.5)

//冒泡排序
#include
using std::swap;
void sort(int* a, int n)
{
bool changed;
do{
changed = false;
for(int i=1; iif(a[i]swap(a[i],a[i-1]);
changed = true;
}
}
--n;
}while(changed);
}


//插入法：比冒泡法要快，时间复杂度和冒泡法是一个级别的
从第二个数据开始，把每个数据插入到适当位置
1.找到适当位置：那个位置左边的数据不比要插的大，或左边无位置
2.插入


void sort(int* a, int n)
{
int j;
for(int i=1; iint t = a[i]; //先把要插入的数据另存一份
for(j=i;j>0&&ta[j]=a[j-1];
a[j] = t;
}
}
//选择法
反复n次，每次在未序数据中最小元素放在第i个位置，跟第i个位置的数据交换
#include
using std::swap;
void sort(int* a, int n)
{
//反复n-1次
for(int i=0; i// 第i次从第i～n个数据中找到最小元素是谁
int min = i;
for(int j=i+1; jif(a[j]min = j;
// 把它跟第i个元素交换
swap(a[min],a[i]);
}
}


//快速法
1.找分界值
2.分组
3.小的值最右边那个跟分界值交换
4.对分界值左右的两组再排序(递归)
当元素个数不超过一个就直接完成

#include
using std::swap;
void sort(int* a, int n)
{
if(n<=1) return;
if(n==2){
if(a[1]return;
}
swap(a[n/2],a[0]); //把分界值交换到最左边
int jie=a[0];
int* L=a+1;
int* R=a+n-1;
while(L{
while(Lwhile(aif(L}
if(*Rsort(a, R-a);
sort(R+1,n-1-(R-a));
}


//主函数
include
using namespace std;
#include
void sort(int* a, int n);

int main()
{
const int N=10240;
int a[N];
for(int i=0; ia[i] = N-i;
for(int i=0; i<10; i++)
cout << a[i] << ' ';
cout << endl;
clock_t t1 = clock(); //clock是取得程序处理使用的时间，比time更精确
sort(a,N);
clock_t t2 = clock();
cout << double(t2-t1)/CLOCKS_PER_SEC << endl; //取得秒数
for(int i=0; i<10; i++)
cout << a[i] << ' ';
cout << endl;
}