摘要
在IT界，，有很多的时候要对于一些数据 ，，进行排序
有时候 可能是 小量的数据 ，，，但是 也有可能是 一些的大数据 ，，，量十分的大。。。
在不同的时候我们对于这些的排序使用的算法是不相同的。。。
我写的这篇文章就是 很好的解析了 这些排序 算法。。。
算法解析
我们经常所说的排序算法，，经常大概有 下面的这几种l;;
下面来我自己实现这些个算法
一、插入排序
插入排序主要分为 直接插入排序 还有 希尔排序 两种
直接插入排序
基本思想：
将一个数据直接插入到已经排好序的有序数据中，从而得到一个新的、个数加一的有序数据。每步将一个待排序的纪录，按其关键码值的大小插入前面已经排序的文件中适当位置上，直到全部插入完为止，，，这就是 所谓的直接插入排序 。
代码的实现
//插入排序
//最坏的情况 (接近逆序)时间复杂度 为 N*N
//最好的情况 (接近升序)时间复杂度 为 N
void InsertSort(int* array,const size_t n)
{
assert(array);
for(size_t i = 1 ;i < n;++i)
{
int tmp = array[i];
int end = i-1;//使用一个end来表示插入的有序数列的位置
//单次排序
while(end>= 0)
{
//插入到一个有序的数列中
if(tmp < array[end])
{
array[end+1] =array[end];
--end;
}
else
{
break;
}
}
//找到位置 ，，将值插入进去
array[end+1] =tmp;
}
}
希尔排序
基本思想：希尔排序也是一种插入排序方法,实际上是一种分组插入方法。
换句话说 就是 ，，在直接插入排序之前 增加一个 预排序 ，，来减少移位的次数
方法就是 ，，，，
先将 数组分成一个gap组
走到此处之后 ；；；就是 直接 改变gap的值 ，，，，直到最后的直接插入排序 ；；；
代码的实现
//希尔排序
//这个算法时间复杂度 不好计算
//时间复杂度大致可知在 为 [N ,N*N];
void ShellSort(int *array,const size_t n )
{
int gap = n;
//排序 直接的插入排序
while(gap > 1)
{
gap = gap/3+1;
//预排序 gap组的数据
for(size_t i = gap;i < n;++i)
{
int tmp =array[i];
int end =i-gap;
//排序 gap间隔的数据
while(end>=0)
{
if(tmp < array[end])
{
array[end+gap] =array[end];
end -= gap;
}
else
{
break;
}
}
array[end+gap] =tmp;
}
}
}
二、选择排序
可以被称作的选择排序的 有两种 ；；；；
选择排序 还有 就是堆排序
选择排序
基本思路：
每一趟从待排序的数据中选出最小（或最大）的一个元素，顺序放在已排好序的数列的最后，直到全部待排序的数据元素排完。
关键点：记住有序数列与无序数列的间隔
思路图：
代码实现
//选择排序
// 时间复杂度 为 N*N
void SelectSort(int * array,const size_t n)
{
assert(array);
int end = n;//end来保存有序和无序的间隔
while(end > 0)
{
end--;
int maxidex = 0 ;
//单趟排序
for(size_t i = 0 ;i <= end;++i)
{
//找到最大的值的下标
if(array[i] > array[maxidex])
{
maxidex = i;
}
}
swap(array[maxidex],array[end]);
}
}
堆排序
堆排序，，，说穿了就是 一个选择排序 ，，，，但是 使用的是堆的数据结构 ，，，找到当前的(未有序的的序列)的最大值(或者是最小值)，放到有序序列中
关键点:建堆 ，交换 ，堆调整
代码实现
1、使用系统库中的函数来实现
//堆排序 直接使用的是 库函数
//时间复杂度 为 N*logN
void HeapSort(int * array,const size_t n)
{
assert(array);
//先建堆
make_heap(array,array+n);
for(size_t i = 0 ;i < n-1;++i)
{
pop_heap(array,array+n-i);
}
}
2、自己实现
//堆排序 自己实现
//需要自己实现一个向下调整的函数
//要是 升序 ，，我们需要建立 一个大堆
//函数有一个假设就是 左右子树 都已经是 大堆
void AdjustDown(int * array, int K,const size_t n)
{
int parent = K; //定义一个父节点的下标
int child = parent *2+1; //得到一个孩子节点的下标
while(child < n)
{
//找到两个孩子中最大的那个节点的下标 给 child
if((child + 1) < n && array[child+1] >array[child])
{
child++;
}
//要是孩子节点的值大于 父节点的值
//将 孩子节点的值 与 父亲节点的值 进行交换
//但会导致 子树的结构不是大堆
//所以要继续向下调整
if(array[child] > array[parent])
{
swap(array[child],array[parent]);
parent =child;
child = parent*2+1;
}
else
{
break;
}
}
}
void HeapSort(int * array,const size_t n)
{
assert(array);
//先对于整个数据 进行建堆
//如果要保证左右子树都是大堆的话，，，就要从第一个非叶子节点进行 调整
for(int i = (n-1-1)/2; i >= 0;--i)
{
AdjustDown(array,i,n);
}
int end = n;//使用 end作为 已经得到的有序 的值 起始下标 初始值 为n；
while(end > 1)
{
--end;
swap(array[0],array[end]);
AdjustDown(array,0,end);
}
}
三、交换排序
交换排序，，，就是将两个数据 进行交换的算法；；；；
冒泡排序
这个算法，，，就是很简单的算法。。。。。
实现起来也很容易 ，，，这里就不细说了 。。。
//冒泡排序
//时间复杂度 为
//最坏的情况(降序的时候 )N*N
//最好的情况(升序 ) N
//但是 相对来说还是 插入排序 更优
void BubbleSort(int *array,const size_t n )
{
assert(array);
for(size_t i = 0 ;i < n-1;++i)
{
//单趟排序
//优化 使用一个数 来记录交换的次数
int j = 0;
int count = 0 ;
for(;j < n-1-i;++j)
{
if(array[j] > array[j+1])
{
swap(array[j],array[j+1]);
count++;
}
}
if(count == 0)//要是交换的次数 为0 表示 已经 是有序的了
break;
}
}
快速排序
这是一个很经典的排序算法 ，，，，很多的算法都是使用此类算法
基本思路：它是由冒泡排序改进而来的。在待排序的n个记录中任取一个记录(通常取第一个记录),把该记录放入适当位置后,数据序列被此记录划分成两部分 。
数组所有元素大小 比该记录小的放到前一部分
，
比它大的放到右边
并把该记录排在这两部分的中间(称为该记录归位),这个过程称作一趟快速排序。
最核心的思想是 左右 分割。
代码实现
//部分 快速排序
//快速排序一般使用的是 递归算法
//[left,right]
int PartSort(int * array,int left,int right)
{
//取一个中间值作为 关键字
int key = right;
while(left < right)
{
//从左边找到一个比关键值大的
while(left<right&& array[left] <=array[key] )
{
++left;
}
//从右边找到一个 比 关键值小的
while(left < right && array[right] >= array[key])
{
--right;
}
swap(array[left],array[right]);
}
swap(array[left],array[key]);
return left;//需要返回一个中间值
}
//[left,right]
void QuickSort(int * array,int left,int right)
{
assert(array);
//如果要是
if(left >= right)
return ;
int ret = PartSort(array,left,right);//得到分割点
//将左边的进行 排序
QuickSort(array,left,ret-1);
//将右边的进行 排序
QuickSort(array,ret+1,right);
}
五、归并排序
基本思路：
把待排序序列分为若干个有序的子序列，再把有序的子序列合并为整体有序序列
。
如设有数列{6，202，100，301，38，8，1}
初始状态：6,202,100,301,38,8，1
第一次归并后：{6,202},{100,301},{8,38},{1}，比较次数：3；
第二次归并后：{6,100,202,301}，{1,8,38}，比较次数：4；
第三次归并后：{1,6,8,38,100,202,301},比较次数：4；
总的比较次数为：3+4+4=11,；
归并排序具体工作原理如下（假设序列共有n个元素）：
将序列每相邻两个数字进行归并操作（merge)，形成floor(n/2)个序列，排序后每个序列包含两个元素
将上述序列再次归并，形成floor(n/4)个序列，每个序列包含四个元素
重复步骤2，直到所有元素排序完毕
代码实现
//归并排序
//假设 两个数组 已有序 ，，，
//然后 将两个数组里的数，，，排序
void _MergeSort(int * array,int * tmp,int left,int right)
{
//当数组只有一个数时 ，，，，为有序
if(left >= right)
{
return ;
}
//让左右两个数组里的数
int mid = left + ((right-left)>>1);
_MergeSort(array,tmp,left,mid);
_MergeSort(array,tmp,mid+1,right);
//到此处说明两个集合的数已经有序
//
int begin1 =left,end1 = mid;
int begin2 = mid+1,end2 = right;
int idex = left;
while(begin1<= end1 && begin2<=end2)
{
if(array[begin1] <= array[begin2])
{
tmp[idex++] = array[begin1++];
}
else
{
tmp[idex++] = array[begin2++];
}
}
while(begin1<= end1)
{
tmp[idex++] = array[begin1++];
}
while(begin2<= end2)
{
tmp[idex++] = array[begin2++];
}
while(left<=right)
{
array[left] = tmp[left];
left++;
}
}
void MergeSort(int * array,const size_t n)
{
int * tmp = new int[n];
_MergeSort(array,tmp,0,n-1);
delete[] tmp;
}
基数排序
基本思想：
它是一种非比较排序。它是根据位的高低进行排序的，也就是先按个位排序，然后依据十位排序……以此类推。
设有一个初始序列为: R {50, 123, 543, 187, 49, 30, 0, 2, 11, 100}。
我们知道，任何一个阿拉伯数，它的各个位数上的基数都是以0~9来表示的。
所以我们不妨把0~9视为10个桶。
我们先根据序列的个位数的数字来进行分类，将其分到指定的桶中。例如：R[0] = 50，个位数上是0，将这个数存入编号为0的桶中。
分类后，我们在从各个桶中，将这些数按照从编号0到编号9的顺序依次将所有数取出来。
这时，得到的序列就是个位数上呈递增趋势的序列。
按照个位数排序： {50, 30, 0, 100, 11, 2, 123, 543, 187, 49}。
接下来，可以对十位数、百位数也按照这种方法进行排序，最后就能得到排序完成的序列。
代码分析
//基数排序
//得到的是 数组最大数 的位数
size_t GetMaxDegit(int * array,const size_t n)
{
int base =10;
int degit = 1;
for(size_t i= 0 ;i < n;++i )
{
while(array[i] >= base)
{
++degit;
base*= 10;
}
}
return degit;
}
//先低位再高位
void LSDSort(int *array,size_t n)
{
int degit = GetMaxDegit(array,n);
int base = 1;
for(size_t j = 0 ;j < degit;++j)
{
int count[10] = {0};
int start[10] = {0};
//记录每个下标的位置
for(size_t i = 0 ;i < n;++i)
{
int num = (array[i]/base)%10;
count[num]++;
}
for(size_t i = 1 ;i < 10;++i)
{
start[i] = count[i-1] +start[i-1];
}
int * tmp = new int[n];
for(size_t i = 0;i < n;++i)
{
int num = (array[i]/base)%10;
tmp[start[num]++] =array[i];
}
memcpy(array,tmp,sizeof(int)*n);
base *= 10;
}
}
//先高位再低位
//单趟排序
//[left,ri]ht] 表示找到高位相等，，，，的数 低位排序
void MSDPartSort(int *array,int left,int right,int base,int n)
{
int count[10] = {0};
int start[10] ={left};
//记录每个位置的数据 的个数
for(size_t i = left ;i <= right;++i)
{
int num = (array[i]/base)%10;
count[num]++;
}
//找到每个位置的起始位置
for(size_t i = 1 ;i < 10;++i)
{
start[i] = count[i-1] +start[i-1];
}
int * tmp = new int[n];
for(size_t i = left;i <= right;++i)
{
int num = (array[i]/base)%10;
tmp[start[num]++] =array[i];
}
memcpy(array+left,tmp+left,sizeof(int)*(right-left+1));
delete[] tmp;
}
void MSDSort(int *array,size_t n)
{
int degit = GetMaxDegit(array,n);
int base = 1;
for(size_t i = 0;i <(degit-1);++i)
{
base *= 10;
}
for(size_t j = 0 ;j < degit;++j)
{
int left = 0;//使用 left表示的是 相同高位的数左下标的
int right =0 ;// 相同高位的右下标
while(right<n)
{
int num1 = array[left]/(base*10);//找到每个数的高位
int num2 =array[right]/(base*10);
if(num1!= num2)//如果要是相等的话
{
MSDPartSort(array,left,right-1,base,n);//将之前的数排序
left =right;//继续向后 寻找 ，高位相等的数
}
else
{
right++;
}
}
if(left != right)//数组走到尽头之后 把但前组的数据排序
{
MSDPartSort(array,left,right-1,base,n);
}
base /=10;//j继续向低位排序
}
}
