简单的排序有5种：直接插入排序，直接选择排序，冒泡排序，快速排序，归并。
排序的稳定性：比如aa 对应10，bb对应20，cc对应20，dd对应30.
如果对数组降序排序，用稳定的算法排列后的字母顺序应该为dd,bb,cc,aa,而不是dd,cc,bb,aa
直接插入排序：
需要两个数组操作，在一个无序的数组中，按顺序每次选一个数，向另一个数组插入到正确的位置。
这种排序是稳定的。
最差时间复杂度O(n^2).
具体代码如下：
#include<stdio.h>
#include<stdlib.h>
int main(){
int *a;
int n;
printf("输入需要排序的总数：");
scanf("%d",&n);
int i;
a=(int *)malloc(sizeof(int)*(n+1));
printf("输入需要排序的数组：");
for(i=0;i<n;i++)
scanf("%d",&a[i]);
int *b;
b=(int *)malloc(sizeof(int)*(n+1));
int j,m=0;
b[0]=a[0];
for(i=1;i<n;i++,m++)
{
for(j=m;j>=0;j--)
{
if(a[i]>b[j])
{
b[j+1]=b[j];
}else{
break;
}
}
j++
b[j]=a[i];
}
for(i=0;i<n;i++)
printf("%d ",b[i]);
return 0;
}
直接选择排序：
在原有的数组上操作。i=0，在i到n的数组上选择一个最小的数和第i个位置交换，然后i++。
这种排序是不稳定的。
最差时间复杂度O(n^2).
具体代码如下:
#include<stdio.h>
#include<stdlib.h>
int main(){
int *a;
int n;
printf("输入需要排序的总数：");
scanf("%d",&n);
int i;
a=(int *)malloc(sizeof(int)*(n+1));
printf("输入需要排序的数组：");
for(i=0;i<n;i++)
scanf("%d",&a[i]);
int j;
for(i=0;i<n-1;i++)
{
int minj=i,min=a[i];
for(j=i+1;j<n;j++)
{
if(min>a[j])
{
min=a[j];
minj=j;
}
}
int temp;
temp=a[minj];
a[minj]=a[i];
a[i]=temp;
}
for(i=0;i<n-1;i++)
printf("%d ",a[i]);
printf("%d",a[i]);
return 0;
}
冒泡排序：
这种排序应该是初学者的首选了，代码简单，具体过程就不多说。
时间复杂度最差也是O（n^2）.
稳定和不稳定的冒泡排序：
#include<stdio.h>
struct stu{
char a[10];
int b;
}str[100];
int main(){
int i,j,n;
scanf("%d",&n);
for(i=0;i<n;i++)
{
scanf("%s%d",str[i].a,&str[i].b);
}
//稳定的冒泡排序
for(i=0;i<n;i++)
for(j=1;j<n-i;j++)
{
if(str[j-1].b<str[j].b)
{
stu t;
t=str[j-1];
str[j-1]=str[j];
str[j]=t;
}
}
//不稳定的冒泡排序
/* for(i=0;i<n-1;i++)
for(j=i+1;j<n;j++)
{
if(str[i].b<str[j].b)
{
stu t;
t=str[i];
str[i]=str[j];
str[j]=t;
}
}*/
for(i=0;i<n;i++)
printf("%s %d\n",str[i].a,str[i].b);
}
归并排序：
归并排序是稳定的排序
时间复杂度恒为O(nlogn)
在之前的已经谈过了，可以看看博主之前那个文章
快速排序：
有两种实现的方法，一种是用sort函数，一种是用递归实现。
sort函数：
在c++里面sort函数的头文件为#include<algorithm>,在c里面也有类似的qsort函数，用法不一样，头文件为include<stdlib.h>。
具体用法在代码里演示：
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
struct stu{
char m[5];
int n;
}p[5];
bool cmp1(int a,int b)
{
return a>b;
}
bool cmp2(stu a,stu b)
{
if(strcmp(a.m,b.m)<0)
return 1;
else
return 0;
}
bool cmp3(stu a,stu b)
{
return a.n<b.n;
}
bool cmp4(stu a,stu b)
{
if(a.n!=b.n)
return a.n<b.n;
else
return strcmp(a.m,b.m)<0;
}
int main()
{
int a[10]={9,6,1,5,8,3,4,7,2,10};
//非结构体排序
//降序
sort(a,a+10,cmp1);
int i;
printf("降序:\n");
for(i=0;i<10;i++)
printf("%d ",a[i]);
printf("\n\n");
//结构体排序
strcpy(p[0].m,"dddd"),p[0].n=10;
strcpy(p[1].m,"cccc"),p[1].n=10;
strcpy(p[2].m,"aaaa"),p[2].n=20;
strcpy(p[3].m,"bbbb"),p[3].n=50;
sort(p,p+4,cmp2);//按字符串升序
printf("字符串升序:\n");
for(i=0;i<4;i++)
printf("%s %d\n",p[i].m,p[i].n);
printf("\n");
strcpy(p[0].m,"dddd"),p[0].n=10;
strcpy(p[1].m,"cccc"),p[1].n=10;
strcpy(p[2].m,"aaaa"),p[2].n=20;
strcpy(p[3].m,"bbbb"),p[3].n=50;
printf("数字升序:\n");
sort(p,p+4,cmp3);//按数字升序
for(i=0;i<4;i++)
printf("%s %d\n",p[i].m,p[i].n);
strcpy(p[0].m,"dddd"),p[0].n=10;
strcpy(p[1].m,"cccc"),p[1].n=10;
strcpy(p[2].m,"aaaa"),p[2].n=20;
strcpy(p[3].m,"bbbb"),p[3].n=50;
printf("数字升序(若数字一样，按字符串升序):\n");
sort(p,p+4,cmp4);
for(i=0;i<4;i++)
printf("%s %d\n",p[i].m,p[i].n);
}
递归实现：
快排是不稳定的。
时间复杂度最坏O(n^2),最佳情况为O(nlogn)。
具体思想可以参考一个讲的很好而且通俗易懂的博客
#include<stdio.h>
int partition(int a[],int low,int high)
{
int part=a[low];
while(low<high)
{
while(a[high]>part&&low<=high)
high--;
while(a[low]<part&&low<=high)
low++;
int t;
t=a[low];
a[low]=a[high];
a[high]=t;
}
int t;
t=a[low];
a[low]=part;
part=t;
return low;
}
void QuickSort(int a[],int low,int high)
{
if(low<high)
{
int part=partition(a,low,high);
QuickSort(a,low,part-1);
QuickSort(a,part+1,high);
}
int Partition(int A[], int low, int high)
{
int pivot = A[low];
while (low < high)
{
while (low < high && A[high] >= pivot)
--high;
A[low] = A[high]; //将比枢轴值小的元素移到左边
while (low < high && A[low] <= pivot)
++low;
A[high] = A[low]; //将比枢轴值小的元素移到右边
}
A[low] = pivot; //将枢轴值元素置于最终位置
return low;
}
void QuickSort(int A[], int low, int high)
{
if (low < high) //递归跳出条件
{
//Partition就是上面的划分操作
int pivot = Partition(A,low,high); //划分
QuickSort(A,low,pivot-1); //左半部分递归
QuickSort(A, pivot + 1, high); //右半部分递归
}
}*/
int main()
{
int a[10]={6,1,2,7,9,3,4,5,10,8};
QuickSort(a,0,9);
int i;
for(i=0;i<10;i++)
printf("%d ",a[i]);
}
