数据结构的排序算法有很多种。
其中，快速排序、希尔排序、堆排序、直接选择排序不是稳定的排序算法；
基数排序、冒泡排序、直接插入排序、折半插入排序、归并排序是稳定的排序算法。
以下整理的5种排序算法
以下是几种排序算法的代码：
选择排序
基本思路：每一趟从待排序的数据元素中选出最小（或最大）的一个元素，顺序放在已排好序的数列的最后，直到全部待排序的数据元素排完。
void select_sort(int * a,int n)
{
int i = 0;
int j = 0;
int temp = 0;
for(i = 0;i < n;i++)
{
for(j = i + 1;j < n;j++)
{
if(a[i] > a[j])
{
temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}
}
return;
}
冒泡排序
基本思路：重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。
void bul_sort(int * a,int n)
{
int i,j,t;
for(j = 1;j < n;j++)
{
for(i = 0;i < n-j;i++)
{
if(a[i] < a[i+1])
{
t = a[i];
a[i] = a[i+1];
a[i+1] = t;
}
}
}
return;
}
归并排序
基本思路：（假设序列共有n个元素）
- 将序列每相邻两个数字进行归并操作，形成n/2个序列，排序后每个序列包含两个元素；
- 将上述序列再次归并，形成n/4个序列，每个序列包含四个元素；
- 重复上一个步骤，直到所有元素排序完毕。
void merge_sort(int * a,int n)
{
if(n > 1)
{
int * list1 = a;
int list1_size = n/2;
int * list2 = a + n/2;
int list2_size = n - list1_size;
merge_sort(list1,list1_size);
merge_sort(list2,list2_size);
merging(list1,list1_size,list2,list2_size);
}
}
void merging(int * list1,int list1_size,int * list2,int list2_size)
{
int temp[N];
int i = 0,j = 0,k = 0,m;//i sui yin list1,j sui yin list2,k sui yin temp
while(i < list1_size && j < list2_size)
{
if(list1[i] < list2[j])
{
temp[k] = list1[i];
k++;
i++;
}
else
{
temp[k] = list2[j];
k++;
j++;
}
}
while(i < list1_size)
{
temp[k] = list1[i];
k++;
i++;
}
while(j < list2_size)
{
temp[k] = list2[j];
k++;
j++;
}
for(m = 0;m < (list1_size + list2_size);m++)
{
list1[m] = temp[m];
}
return;
}
快速排序
基本思路：
快速排序是找出一个元素作为基准，然后对数组进行分区操作，使基准左边元素的值都不大于基准值，基准右边的元素值都不小于基准值，如此作为基准的元素调整到排序后的正确位置。
void quik_sort(int * a,int n)
{
if(n < 2)
{
return;
}
int low = 0;
int high = n - 1;
int key = a[0];
while(low < high)
{
while(low < high && key < a[high])
{
high--;
}
if(low < high)
{
a[low] = a[high];
low++;
}
while(low < high && key > a[low])
{
low++;
}
if(low < high)
{
a[high] = a[low];
high--;
}
}
a[low] = key;
quik_sort(a,low);
quik_sort(a+low+1,n-low-1);
}
