以下排序均为从小到大排序
main函数：
#include<stdio.h>
#include <iostream>
#include<math.h>
int a[10000];
void quicksort(int left,int right);
void Bubblesort(int num);
void Bubblesort_2(int num);
void ShellSort(int len);
void merge(int l,int mid,int r);
void mergesort(int n);
int main()
{
int i,j,temp,num,len,pos;
printf("请输入要排序数字的总数：\n");
scanf("%d",&num);
printf("请输入要排序的数据：\n");
for(i=0;i<num;i++){
scanf("%d",&a[i]);
}
//快排
quicksort(0,num-1);
//冒泡
//Bubblesort(num);
//双冒泡
//Bubblesort_2(num);
//希尔
//ShellSort (num);
//归并
//mergesort(num);
for(i=0;i<num;i++){
printf("%d ",a[i]);
}
}
这里记录一个使用gdb的小知识：
可以用下面的方法来显示数组
p *array@len
其中p相当于print，array就是数组首地址，也可以是数组名，len是想要显示的数组的长度。
比如我有一个数组的定义
int a[] = {1, 2, 3, 4, 5};
那么想要显示的时候就可以写：
p *a@5
这样就会显示数组a中的所有元素。
也可以使用display在一部调试的时候都显示：
display *a@5
取消显示就用undisplay，不过这时候要写显示的号码。
这样在调试程序的时候就可以很直观地看到数组的变化情况了
1.快速排序
void quicksort(int left,int right){
int i,j,t,temp;
if (left >right) //从左和从右出发的标记交叉了
return;
temp = a[left]; //保存获得基准数，以备后面交换
i = left;
j = right;
while(i < j){
//这里一定要从基准数选择的另一边先开始
while(a[j] >= temp && i < j) j--; //寻找右侧比基准数小的数
while(a[i] <= temp && i < j) i++; //寻找左侧比基准数大的数
//交换数字
if(i < j){
t = a[i];
a[i] = a[j];
a[j] = t;
}
}
a[left] = a[i]; //将 i 位置与基准数调换位置
a[i] = temp; //将基准数放在i的位置，此时左边的数都比a[i]小，右边的数都比a[i]大
//将数组一分为二，继续进行排序
quicksort(left,i-1);
quicksort(i+1,right);
return;
}
这里有个小知识点，寻找目标的指针为什么要从基准数的另一边先开始找呢：
从从小到大的排序规则来看，这么做是为了保证右边指向的数字要小于等于基准数字。
2.冒泡排序
优化过版
void Bubblesort(int num){
int i,pos,j,temp;
i=num-1; //初始时，长度-1
while(i){
pos=0; //每趟开始，无记录交换
for(j=0;j<i;j++){
if (a[j]>a[j+1]){
pos=j; //记录交换位置
temp=a[j];
a[j]=a[j+1];
a[j+1]=temp;
}
}
i=pos; //为下一趟排序作准备
}
}
鸡尾酒排序（双冒泡排序）
void Bubblesort_2(int num){
int i,temp;
int left = 0,right = num-1;
while(left < right){
for (i = left;i < right;i++){ //最大的放在最右侧
if(a[i] > a[i+1]){
temp = a[i];
a[i] = a[i+1] ;
a[i+1] = temp;
}
}
right--;
for(int j = right;j > left;j--){//最小的放在最左侧
if(a[j-1] > a[j]){
temp = a[j];
a[j] = a[j-1] ;
a[j-1] = temp;
}
}
left++;
}
}
3.希尔排序
上面提到的插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位。
但是插入排序有一个特点，就是对几乎已经排好序的数据进行操作时，效率高，即可以达到线性排序的效率。
所以便有了一个名叫希尔的大神，根据这一特点改良了这一排序方法，通过分组形式，对分组进行一次次简单插入排序，使每一次重新分组后的数据，都更加接近几乎排好序列的一串数据，使得排序一次比一次简单，这样便大大降低了简单插入排序的复杂度。
希尔排序的核心在于分组，我们分别将相邻 step 的数字分别分成一组，然后对每一组组内进行简单插入排序，每次分的组都会更少，组内数据更多，同时整体更加接近排好的数据，
详细见代码：
void ShellSort (int a[],int len){
int step,temp,i,j,k;
for(step = len/2;step > 0;step /= 2){ //设置同一组成员之间间隔大小step
for(i = 0;i < step;i++){//控制对第i组进行简单插入排序
for(j = i + step;j < len;j+=step){//用循环找到自己组别的成员进行一次简单插入排序
if(a[j] < a[j-step]){
temp = a[j];
k = j - step;
while(k >= 0 && a[k] > temp){
a[k+step] = a[k];
k-=step;
}
a[k+step] = temp;
}
}
}
}
}
希尔排序的时间复杂度与选取的增量有关，所以希尔排序时间复杂度并不稳定，选取合适的增量可减少时间复杂度。
4.归并排序
核心思想是将两个有序的数列合并成一个大的有序的序列。通过递归，层层合并，即为归并
看下面这幅图就很明了了：
void merge(int l,int mid,int r)
{
int aux[r-l+1];//开辟一个新的数组，将原数组映射进去
for(int m=l;m<=r;m++)
{
aux[m-l]=a[m];
}
int i=l,j=mid+1;//i和j分别指向两个子数组开头部分
for(int k=l;k<=r;k++)
{
if(i>mid)
{
a[k]=aux[j-l];
j++;
}
else if(j>r)
{
a[k]=aux[i-l];
i++;
}
else if(aux[i-l]<aux[j-l])
{
a[k]=aux[i-l];
i++;
}
else
{
a[k]=aux[j-l];
j++;
}
}
}
void mergesort(int n)
{
for(int sz=1;sz<=n;sz+=sz)
{
for(int i=0;i+sz<n;i+=sz+sz)//i+sz防止越界
{//对arr[i...sz-1]和arr[i+sz.....i+2*sz-1]进行排序
merge(i,i+sz-1,std::min(i+sz+sz-1,n-1)); //min函数防止越界
}
}
}