文章目录
零、概述
0.1、排序算法
简单排序算法：选择排序、冒泡排序、插入排序
复杂一点的算法：快速排序、堆排序、归并排序。希尔排序、桶排序(计数排序、基数排序)
0.2、结构代码
#include "stdlib.h"
#include "stdio.h"
//三元表达式G++编译通过，GCC编译不通过，所以改为了&&
#define SWAP(x,y) ((x!=y)&&(x=x^y, y=x^y, x=x^y))
#define N 10
/*---------------
*----排序算法----
*---------------/
void print(const int data[],int length)
{
for (int i = 0; i < length; ++i)
printf("%d ",data[i] );
printf("\n");
}
int main(int argc, char const *argv[])
{
int data[N] ;
for(int i=0;i<N;i++)
data[i] = rand()%(100*N);
print(data,N);
//QuickSort(data,N,0,N-1);
print(data,N);
return 0;
}一、选择排序
1.1、思想
1、每次循环选择未排序序列中最小(大)的元素，插入到已排序序列的末尾；
一般思路，选取小的，所以先排完的是小端。
2、时间复杂的：O(n*n) 空间复杂度：O(1)
1.2、实现
void SelectSort(int *numbers, int n)
{
if(n<=0 || numbers == NULL)
exit(0);
for(int i=0; i<n-1; i++)
{
int min = i;
for(int j=i+1; j<n; j++)
{
if(numbers[j] < numbers[min]) //选择最小的
min = j;
}
if(i!=min)
swap(numbers[i],numbers[min]);
}
}1.3、注意
1、简单选择排序比较次数与序列的初始排序无关。 若待排序有 N 个元素，则比较次数总是N (N – 1) / 2。
2、而移动次数与序列的初始排序有关。当序列正序时，移动次数最少，为 0.
3、当序列反序时，移动次数最多，为3N (N – 1) / 2。
二、冒泡排序
2.1、思想
1、冒泡排序原理是临近的数字两两进行比较,按照从小到大或者从大到小的顺序进行交换,这样一趟过去后,最大或最小的数字被交换到了最后一位。每趟排序过程中通过两两比较，找到第 i 个小（大）的元素，将其往上排。
2、时间复杂的：O(n*n) 空间复杂度：O(1)；
2.2、实现
void BubbleSort(int *numbers,int n)
{
if(n<=0 || numbers == NULL)
exit(0);
for(int i=0; i<n-1; i++)
{
for(int j=i+1;j<n;j++)
{
if(numbers[i]>numbers[j])
swap(numbers[i],numbers[j]); //一层层向上冒泡
}
}
}2.3、注意
1、改进方法是加入标志性变量exchange，用于标志某一趟排序过程中是否有数据交换。如果进行某一趟排序时并没有进行数据交换，则说明所有数据已经有序，可立即结束排序，避免不必要的比较过程。
2、冒泡排序是一种交换排序。
三、插入排序
3.1、思想
1、取未排序序列的头部第一个元素，然后在已排序的序列中依次比较，找到自己的位置。类似与打牌时给自己手里的牌排序。
2、时间复杂的：O(n*n) 空间复杂度：O(1)
3.2、实现
void InsertSort(int *numbers, int n)
{
if(n<=0 || numbers == NULL)
exit(0);
for(int i=1; i<n; i++)
{
int key = numbers[i];
int j=i;
for(; j>0 && numbers[j-1] > key; j--)
{
numbers[j] = numbers[j-1];
}
numbers[j] =key;
}
}3.3、注意
1、技巧：带哨兵的查找；
2、假改进：查找是二分查找，因为数组最后还要移动元素，虽然找到位置快，但是移动并没有改进；
3、当数据正序时，执行效率最好，每次插入都不用移动前面的元素，时间复杂度为O(N)。
当数据反序时，执行效率最差，每次插入都要前面的元素后移，时间复杂度为O(N2)。
所以，数据越接近正序，直接插入排序的算法性能越好。
四、快速排序
4.1、思想
1、通过一趟排序，去一个基点，将要排序的数据分割成独立的两部分：分割点左边都是比它小的数，右边都是比它大的数。然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
每一趟都会确定所选取那个基点的最终位置。也只能确定那一个元素的位置。
4.2、实现
int Partition(int data[],int length,int start,int end)
{
if(data == NULL || length <=0 || start <0 || end <0 || end >= length)
exit(0);
int index = (end + start)/2;//也可以是随机数，防止近似序列时效率低
int small = start -1;
SWAP(data[index],data[end]);
for(index = start; index<end; index++)
{
if(data[index]<data[end])
{
small++;
if(small != index)
SWAP(data[index],data[small]);
}
}
//之前指向小集合的最后一个元素，加了之后就是大集合的第一个元素
small++;
//，然后和end的中数交换；此时中数在排完后的序列中位置就是这个
SWAP(data[small],data[end]);
return small;
}
void QuickSort(int data[],int length,int start,int end)
{
if(start == end)
return;
int index = Partition(data,length,start,end);
if(index>start)
QuickSort(data,length,start,index-1);
if(index<end)
QuickSort(data,length,index+1,end);
}4.3、注意
1、快速排序是一种交换排序；
2、当数据有序时，以第一个关键字为基准分为两个子序列，前一个子序列为空，此时执行效率最差，O(n^2)。
而当数据随机分布时，以第一个关键字为基准分为两个子序列，两个子序列的元素个数接近相等，此时执行效率最好。所以，数据越随机分布时，快速排序性能越好；数据越接近有序，快速排序性能越差。
五、堆排序
5.1、思想
1、主要分为构建堆，和交换过程
5.2、实现
//调整堆
void AdjustHeap(int data[], int parent, int length)
{
if(data == NULL || parent <0 || parent>=length)
return;
int tmp = data[parent];
int child = parent*2+1;
while(child<length)
{
if(child+1<length && data[child+1]>data[child])
child++;
if (data[child]<tmp)
break; //此时还是符合大顶堆的结构的,退出
//此时不符合大顶堆，则将大孩子上移动
data[parent] = data[child];
//指针下移，循环检验调整后的子树是否符合大顶堆【此处也可以递归实现】
parent = child;
child = parent*2 +1;
}
data[parent] = tmp;
return;
}
void HeapSort(int data[],int length)
{
//初始化堆
for (int i=length/2; i>=0; --i) //此处注意
AdjustHeap(data,i,length);
for (int i = length-1; i>=0; --i)
{
SWAP(data[0],data[i]);
AdjustHeap(data,0,i);
}
}5.3、注意
1、堆是一棵顺序存储的完全二叉树；
A、其中每个结点的关键字都不大于其孩子结点的关键字，这样的堆称为小根堆。
其中每个结点的关键字都不小于其孩子结点的关键字，这样的堆称为大根堆。
B、设当前元素在数组中以R[i]表示，那么，
(1) 它的左孩子结点是：R[2*i+1];
(2) 它的右孩子结点是：R[2*i+2];
(3) 它的父结点是：R[(i-1)/2]; //向下取整
(4) R[i] <= R[2*i+1] 且 R[i] <= R[2i+2]。
2、当想得到一个序列中第k个最小的元素之前的部分排序序列，最好采用堆排序。因为堆排序的时间复杂度是O(n+klog2n)，若k≤n/log2n，则可得到的时间复杂度为O(n)。
六、归并排序
6.1、思想
基本思路就是将数组分成二组A，B，如果这二组组内的数据都是有序的，那么就可以很方便的将这二组数据进行排序。如何让这二组组内数据有序了？
可以将A，B组各自再分成二组。依次类推，当分出来的小组只有一个数据时，可以认为这个小组组内已经达到了有序，然后再合并相邻的二个小组就可以了。这样通过先递归的分解数列，再合并数列就完成了归并排序。
6.2、实现
void MergeArry(int data[],int first,int mid,int last)
{
int i = first,j = mid+1,k=0;
int *tmp = (int*) malloc((last-first+1)*sizeof(int));
//将数组a的mid前半部分和后半部分，合并排序到tmp中
while(i<=mid && j<=last)
{
if(data[i] <= data[j])
tmp[k++] = data[i++];
else
tmp[k++] = data[j++];
}
while(i<=mid)
tmp[k++] = data[i++];
while(j<=last)
tmp[k++] = data[j++];
//将tmp数组中的数返回赋值给a,现在a就部分有序了
for(i=0; i<k; i++)
data[first+i] = tmp[i];
free(tmp);
}
void MergeSort(int data[], int first, int last)
{
if(data ==NULL || first<0 || last<0 )
return;
if(first < last)
{
int mid = (first+last) / 2;
MergeSort(data,first,mid); //前半部分
MergeSort(data,mid+1,last); //后半部分
MergeArry(data,first,mid,last);
}
}6.3、注意
1、因为归并排序每次都是在相邻的数据中进行操作，所以归并排序在O(N*logN)的几种排序方法（快速排序，归并排序，希尔排序，堆排序）也是效率比较高的。
七、其他排序
7.1、希尔排序
7.2、桶排序思想
7.3、基数排序
7.4、计数排序
八、各种排序对比
1、对比表
2、关于时间复杂度：
A、平方阶(O(n^2))排序
各类简单排序:直接插入、直接选择和冒泡排序；
B、线性对数阶(O(nlog2n))排序
快速排序、堆排序和归并排序；
C、O(n1+§))排序,§是介于0和1之间的常数。
希尔排序
D、线性阶(O(n))排序
基数排序，此外还有桶、箱排序。
3、关于空间复杂度
4、关于稳定性：
稳定的排序算法：冒泡排序、插入排序、归并排序、基数排序、计数排序、桶排序
不稳定排序算法：选择排序、快速排序、希尔排序、堆排序
九、参考
1、http://www.cnblogs.com/jingmoxukong/p/4329079.html
转载标明出处：https://blog.evanxia.com/2015/11/318
