#pragma once
#include<iostream>
#include<assert.h>
using namespace std;
//直接排序：指的是设定2个下标/指针。然后从下标1开始进行比较，
//升序情况下：若在前的下标/指针大于当前比较数值。就进行数组的后移。
//直到满足当前序列值。然后最终将当前比较数值进行替换。
//PS：总有一个指针遍历比较数组（k，arry[i]）
//时间复杂度为：0（n^2）,空间复杂度0（1）
void InsertSort(int* arry,int len)
{
assert(arry);
for(int i = 1; i < len;++i)
{
int j = i-1;
int k = arry[i];
while(j > -1 && arry[j] > k)
{
arry[j + 1] = arry[j];
--j;
}
arry[j+1] = k;
}
}
//希尔排序：在直接排序的基础上增加分组Gap值，
//利用Gap值，比较对应（len/gap）* i的位置。每个位置代表一个分组
//然后将i的值依次增加到len-gap的位置相当于我已经比较了每个对应分组，使当前序列趋近于有序。
//然后我们缩小gap值的范围，使其接近于2，证明还需要进行分组排序。
//0(n^2),0(1);
void ShellSort(int *arry,int len)
{
assert(arry);
int gap = len;
while(gap > 1)
{
gap = gap/3 + 1;
for(int i = 0; i < len - gap;++i)
{
int j = i;
int k = arry[i+gap];
while(j > -1 && arry[j] > k)
{
arry[j + gap] = arry[j];
j -= gap;
}
arry[j+gap] = k;
}
}
}
//选择排序：其实这个排序的思路比较简单，我们只需要每次遍历数组
//得到最小/最大（或者2者都选），然后将最大值最小值分别丢到数组的最左端还有最右端然后缩小范围就可以了。
//然后值得注意的是。我们在同时得出当前最大最小值时候，需要注意
//当前选出的最大值最小值在进行其中一次交换后，会不会将max与min相交换。
//0（n^2）,0(1)
void SelectSort(int *arry, int len)
{
assert(arry);
for(int i = 0, j = len-1;i < j;++i,--j)
{
int min = i;
int max = j;
for(int k = i;k <= j;++k)
{
if(arry[k] < arry[min])
{
min = k;
}
if(arry[k] > arry[max])
{
max = k;
}
if(min != i)
{
int temp = arry[min];
arry[min] = arry[i];
arry[i] = temp;
if(max == i)
max = min;
}
if(max!= j)
{
int temp = arry[max];
arry[max] = arry[j];
arry[j] = temp;
}
}
}
}
//冒泡排序：冒泡排序比较简单，就不多说了。
//需要注意的是我们可以利用一个标记值来确定我们需不需要进行这一次的冒泡
//如果需要进行冒泡的话我们的标记值就会设置位开关。
//然后我们就可以减少我们所需要排序的次数。
//0(n^2),0(1)
void BubbleSort(int *arry,int len)
{
assert(arry);
for(int i = 0;i < len -1;++i)
{
for(int j = len - 1;j >= i;--j)
{
if(arry[j] < arry[j-1])
{
int temp = arry[j];
arry[j] = arry[j - 1];
arry[j - 1] = temp;
}
}
}
}
//快速排序：我们快速排序的大概思路就是选择一头一尾的2个下标/指针,然后我们利用指针选择法
//将大数与小数集中排列。将我们所选的key值建为关键值，大于放左边，小于放右边。然后不断缩小范围就好了
//提高效率的办法就是我们可以在当前序列的值小于某个数值的时候我们选择使用插入排序。
//这可以有效的提高我们排序的效率。
//一前一后只适用于数组。
//0（nlogn）,0(logn)
int _QuickSort(int* arry,int left,int right)
{
assert(arry);
if(left >= right)
return 0;
int tmp = arry[right];
int index = right;
--right;
while(left <right)
{
while(left < right && arry[left] <= tmp)
++left;
while(left < right && arry[right] >= tmp)
++right;
if(left < right)
{
swap(arry[left],arry[right]);
}
}
if(tmp <= arry[right])
{
swap(arry[right],arry[index]);
}
return right;
}
void QuickSort(int *arry,int left,int right)
{
assert(arry);
if(left < right)
{
int mid = _QuickSort(arry,left,right);
QuickSort(arry,mid+1,right);
QuickSort(arry,left,mid-1);
}
}
//快速排序：前后指针，我们选择一个紧紧跟随的2个指针，原理跟一前一后相同，知识进行了大数小数的堆置、
//这样的方法可以利用到指针中，当然了，key值得选择很重要，
//最坏的情况就是选择到了有序数组的最大数/最小数，就会出现最坏的情况。
//选择3数取中法可以有效地避免这个情况的出现。
void swap(int* arry,int left,int right)
{
int tmp;
tmp = arry[left];
arry[left] = arry[right];
arry[right] = tmp;
}
void QuickSort_On(int* arry,int left,int right)
{
int i,last;
if(left >= right)
return ;
swap(arry,left,(left+(right-left)/2));
last = left;
for(i = left +1;i <= right;++i)
{
if(arry[i] < arry[left])
swap(arry,++last,i);
}
swap(arry,left,last);
QuickSort_On(arry,left,last - 1) ;
QuickSort_On(arry,last +1,right);
}
//归并排序：利用树的分支然后在利用区间的整合，实现排序完成。
//每次我们确定一个区间（n/2），然后不断进行2分的拆分。
//在没2个区间中我们进行比较排序，对每个区间的首部进行比较，然后规整到我们需要保存的数组中。
//最后我们通过不断的拆分，不断地归并复制，就可以出现相对的排序序列了。
//0（nlogn）,0（n）
void Merge(int* arry,int* dest,int begin1,int end1,int begin2, int end2)
{
int index = begin1;
while(begin1 <= end1 && begin2 <= end2)
{
if(arry[begin1] < arry[begin2])
{
dest[index++] = arry[begin1++];
}
else
{
dest[index++] = arry[begin2++];
}
}
if(begin1 <= end1)
{
while(begin1 <= end1)
{
dest[index++] = arry[begin1++];
}
}
else
{
while(begin2 <= end2)
dest[index++] = arry[begin2++];
}
}
void _Merge(int* arry,int* dest, int left,int right)
{
//因为是左闭右开。
int mid = left+((right - left) /2);
if(left < right -1)
{
//int mid = left+((right - left)>>1);
_Merge(arry,dest,left,mid);
_Merge(arry,dest,mid+1,right);
Merge(arry,dest,left,mid,mid+1,right);
//memcpy(arry+left,dest+left,sizeof(int)* (right - left +1));
}
Merge(arry,dest,left,mid,mid+1,right);
memcpy(arry+left,dest+left,sizeof(int)* (right - left +1));
}
void MergeSort(int *arry,size_t size)
{
int* dest = new int[size];
_Merge(arry,dest,0,size-1);
//memcpy(arry,dest,sizeof(int)* (11));
delete[] dest;
}总结：
其中时间复杂度为nlogn的有快速排序，归并排序，堆排序。其中快速排序最坏的情况是n^2,其余都是n^2,希尔排序介于n-n^2之间。
对于稳定性来说，冒泡排序，插入排序，归并排序是稳定的，其他的排序在不同的情况下稳定性会不同。
对于空间复杂度来说，快速排序的空间复杂度是0（logn），归并排序是0（n）
下面是只能在限定条件里面使用的基数排序和计数排序：
计数排序:时间复杂度:O(N), 空间复杂度O(最大数-最小数)
基数排序:时间复杂度:O(N*位数)，空间辅助度O(N)
//基数排序：利用哈希桶原理把数据排序，可选择从低位到高位或从高位到低位
//利用稀疏矩阵压缩存储进行数据定位
int GetDigit(int* arr, size_t size)
{
int maxDigit = 1;
int maxNum = 10;
for (int i = 0; i < size; ++i)
{
if (arr[i] >= maxNum)
{
int count = maxDigit;
while (maxNum <= arr[i])
{
maxNum *= 10;
++count;
}
maxDigit = count;
}
}
return maxDigit;
}
void LSDSort(int* arr, size_t size)//从低位开始排 MSD从高位开始排
{
int counts[10] = { 0 };//存位数对应数据个数
int startCounts[10] = { 0 };
int *bucket = new int[size];
int digit = 1;//表示先取各位
int maxDigit = GetDigit(arr, size);
int divider = 1;//除数
while (digit++ <= maxDigit)
{
memset(counts, 0, sizeof(int) * 10);
memset(startCounts, 0, sizeof(int) * 10);
for (int i = 0; i < size; ++i)
counts[(arr[i]/divider)% 10]++;
for (int i = 1; i < 10; ++i)
startCounts[i] = startCounts[i - 1] + counts[i - 1];
for (int i = 0; i < size; ++i)
{
bucket[startCounts[(arr[i] / divider) % 10]++] = arr[i];
}
divider *= 10;
memcpy(arr, bucket, sizeof(int)*size);
}
memcpy(arr, bucket, sizeof(int)*size);
delete[] bucket;
}
//计数排序
void CountSort(int *arr, size_t size,int len)
{
int* bitMap = new int[len];
memset(bitMap, 0, sizeof(int)*len);
for (int i = 0; i < size; ++i)
{
int index = arr[i] >>5;//除以32
int count = arr[i] % 32;
bitMap[index] |= (1 << count);
}
int index = 0;
for (int i = 0; i < len; ++i)
{
int count = 0;
while (count <32&&index<size )
{
if (bitMap[i] & (1 << count))
arr[index++] = i * 32 + count;
++count;
}
}
delete[] bitMap;
}这两个排序的使用环境只能够在特定的条件下使用，所以没有纳入常规的排序手法中，但是可以看出他的效率十分惊人。
免责声明：本站发布的内容（图片、视频和文字）以原创、转载和分享为主，文章观点不代表本网站立场，如果涉及侵权请联系站长邮箱：is@yisu.com进行举报，并提供相关证据，一经查实，将立刻删除涉嫌侵权内容。
