排序算法：
基本：冒泡，快速，选择，堆，插入，shell
多路并归：
1.冒泡排序：
思想：交换排序，通过相邻的交换来达到排序的目的。
流程：
1.对数组中的各数据，依次比较相邻两个元素的大小。
2.如果前面的大，交换。经过一轮，可把最小的排好。
3.然后用同样的方法，把剩下的数据排好。最后从小到大排好相应的数据。
#include <iostream>
#include <time.h>
#define SIZE 10
using namespace std;
void BubbleSort(int *a,int len)
{
int temp;
for(int i=0;i<len-1;i++)
{
for(int j=len-1;j>i;j--)
{
if(a[j-1]>a[j])
{
temp=a[j];
a[j]=a[j-1];
a[j-1]=temp;
}
}
cout<<i<<":";
for(int k=0;k<len;k++)
{
cout<<a[k]<<" ";
}
cout<<endl;
}
}
int main()
{
int shuzu[SIZE];
srand(time(NULL));//随机种子
for(int i=0;i<SIZE;i++)
{
shuzu[i]=rand()/1000+100;
}
cout<<"old:";
for(int i=0;i<SIZE;i++)
{
cout<<shuzu[i]<<" ";
}
cout<<endl;
BubbleSort(shuzu,SIZE);
cout<<"now:";
for(int i=0;i<SIZE;i++)
{
cout<<shuzu[i]<<" ";
}
cout<<endl;
}
选择排序：
思路：在每一步选取最小的来重新排列。
流程:
1.首先从原始数据中选中最小的一个，和位于第一个位置的数据交换、
2.接着从剩下的n-1数据中选择次小的，与第二个位子交换。
3.这样重复，数组从小到大排列。
#include <iostream>
#include <time.h>
using namespace std;
#define SIZE 10
void SelectionSort(int *a,int len)
{
int temp,k;
for(int i=0;i<len-1;i++)
{
k=i;
for(int j=i+1;j<len-1;j++)
{
if(a[j]<a[k])
k=j;
}
if(k!=i)//交换
{
temp=a[k];
a[k]=a[i];
a[i]=temp;
}
}
}
int main()
{
int shuzu[SIZE];
srand(time(NULL));
for(int i=0;i<SIZE;i++)
{
shuzu[i]=rand()/1000+100;
}
cout<<"old:";
for(int i=0;i<SIZE;i++)
{
cout<<shuzu[i]<<" ";
}
cout<<endl;
SelectionSort(shuzu,SIZE);
cout<<"now:";
for(int i=0;i<SIZE;i++)
{
cout<<shuzu[i]<<" ";
}
cout<<endl;
}
插入排序：
思路：通过未排序的数据逐个插入合适的位置来完成工作。
流程：
1.首先对数组的前两个数据进行从小到大排序
2.接着第3个数据插入合适的位子
3.第4个
4.重复
#include <iostream>
#include <time.h>
#define SIZE 10
using namespace std;
void InsertionSort(int *a,int len)
{
int temp,j,i,k;
for(i=1;i<len;i++)
{
//temp=a[i],a[j+1]=a[j];a[j+1]=temp;就是个交换。 判断 j-- 为逻辑
temp=a[i],
j=i-1;
while(j>=0 && temp<a[j])
{
a[j+1]=a[j];
j--;
}
a[j+1]=temp;
}
}
int main()
{
int arr[SIZE];
srand(time(NULL));
for(int i=0;i<SIZE;i++)
{
arr[i]=rand()/1000+100;
}
cout<<"old:";
for(int j=0;j<SIZE;j++)
{
cout<<arr[j]<<" ";
}
cout<<endl;
InsertionSort(arr,SIZE);
cout<<"now:";
for(int k=0;k<SIZE;k++)
{
cout<<arr[k]<<" ";
}
cout<<endl;
}
Shell排序：（希尔排序，缩小增量排序）
流程
1.将有n个元素的数组，分成n/2个数字序列。第一个数据和第n/2+1成一对、。。。
2.一次循环是每个序列对排好顺序
3。然后，在变为n/4
4.不断重复。
#include <iostream>
#include <time.h>
using namespace std;
#define SIZE 10
void ShellSrot(int *a,int len)
{
int i,j;
int r,temp;
for(r=len/2;r>=1;r/=2)
{
for(i=r;i<len;i++)
{
temp=a[i];
j=i-r;
while(j>=0&&temp<a[j])
{
a[j+r]=a[j];
j-=r;
}
a[j+r]=temp;
}
}
}
int main()
{
int arr[SIZE];
srand(time(NULL));
for(int i=0;i<SIZE;i++)
{
arr[i]=rand()/1000+100;
}
cout<<"old:";
for(int j=0;j<SIZE;j++)
{
cout<<arr[j]<<" ";
}
cout<<endl;
ShellSrot(arr,SIZE);
cout<<"now:";
for(int k=0;k<SIZE;k++)
{
cout<<arr[k]<<" ";
}
cout<<endl;
}