//排序算法
//1.堆排序 2.插入排序 3.希尔排序 4.选择排序 5.快速排序 6.归并排序 7.冒泡排序
// 1.堆排序 向下调整 （选择排序的一种）不稳定
//时间复杂度 O(n*lgn)
//空间复杂度 O(1)
//从最后一个父节点开始向前遍历，边遍历边向下调整，（这样保证最下面的大数据可以每次向下调整时都向上移动）
//最后将最大的数与最后的数交换
void adjustdown(int*a,int parent,int size) //一次向下调整 堆排序
{
assert(a);
int child = parent * 2 + 1;
while (child < size)
{
if (child + 1 < size && a[child + 1] > a[child])
child++;
if (a[child]>a[parent])
{
swap(a[child], a[parent]);
parent = child;
child = parent * 2 + 1;
}
else
break;
}
}
int a[]={5,4,3,2,1};
int end = sizeof(a) / sizeof(a[0]);
for (int k = (end-2) / 2; k >= 0; k--)//从最后一个父节点开始向前遍历
{
adjustdown(a,k,end);
}
for (int j = 0; j < sizeof(a) / sizeof(a[0]); j++)
{
/*adjustdown(a, 0, end);*/
swap(a[0], a[end - 1]);
end--;
adjustdown(a, 0, end);
}
// 2.插入排序 稳定（相同元素的相对位置不变）
// 从第二个数开始，认为前面是有序序列。向前插入
void insertsort(int* a,int size) //插入排序
{
for (int i = 0; i < size - 1; i++)
{
int end = i;//有序序列的结尾
int tmp = a[end + 1];
while (end >= 0)
{
if (tmp < a[end])//
{
a[end + 1] = a[end];
end--;
}
if (end<0||tmp>a[end]) //关键 到了最前面 或者 不能再向前了，就插入
{
a[end + 1] = tmp;
break;
}
}
}
}
// 3.希尔排序 插入排序最坏情况下改进版 不稳定
// 利用 增量gap 分组，gap从 size/2 开始，每次 /2,继续分组，知道gap是1的时候，就是一个简单的直接插入排序
// 时间复杂度平均是O(n^1.3),最好是 O(n) ,最差 O(N^2);
// 空间复杂度 o(1), 就在原数组操作
void insertsort(int* a ,int size) //希尔排序 一次
{
int gap = size;
while(gap > 0)
{
gap/=2;//每次 /2
for (int i = 0; i < size - gap; i++)
{
int end = i;
int tmp = a[end + gap]; //注意gap
while (end >= 0)
{
if (tmp < a[end])
{
a[end + gap] = a[end];
end=end-gap; //注意gap
}
if (end<(i%gap) || tmp>a[end]) //注意gap
{
a[end + gap] = tmp; //注意gap
break;
}
}
}
}
}
// 4.选择排序 不稳定
// 从下标0开始，每次从后面选出一个最小数放到当前序列最前面
// 时间复杂度 O(n^2) 都要选择一遍
// 空间复杂度 O(1)
void SelectSort(int* a, int n)//选择排序
{
int min, k;
for (int i = 0; i < n-1; i++)
{
min = a[i]; k = i; //要记住这个下标，后面好交换
for (int j = i+1; j < n; j++)
{
if (a[j] < min)
{
min = a[j];
k = j;
}
}
if (k != i)
swap(a[i],a[k]);
}
}
// 5.快速排序 非递归
// 思路：每次将区间左右下标存进栈里，然后取出栈顶上的一对下标，排序，返回下标 。然后分区间 。循环
int _QuickSort4(int* a, int left, int right)//快速排序 非递归
{
int &key = a[right];
while (left < right)
{
while (left < right&&a[left] <= key)
{
left++;
}
while (left < right&&a[right] >= key)
{
right--;
}if (left < right)
swap(a[left],a[right]);
}swap(a[left], key);
return left;
}
void QuickSort4(int* a, int left, int right)
{
stack<int> s; //将当前的左右下标存进栈中
s.push(right);
s.push(left);
while (!s.empty())
{
int begin = s.top(); //取出左右下标
s.pop();
int end = s.top();
s.pop();
int div = _QuickSort4(a, begin, end); //对当前区间 快速排序一次
if (begin < div - 1) //插入左区间的左右下标
{
s.push(div-1);
s.push(begin);
}
if (div + 1 < end) //插入右区间的左右下标
{
s.push(end);
s.push(div+1);
}
}
}
// 快速排序 左右指针法 最常规做法
//通过一趟排序将要排序的数据分割成独立的两部分，
//其中一部分的所有数据都比另外一部分的所有数据都要小，
//然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
// 思路：拿出一个数做基准key，分别从最后找出小于key和前面找出大于key的数交换他们，最后交换这个key和left(=right)
int _QuickSort1(int *a,int left,int right)//左右指针法
{
if (left<right)
{
int &key = a[right];
while (left < right)
{
while (left < right&&a[left] <= key)
{
left++;
}
while (left < right&&a[right] >= key)
{
right--;
}
if (left!=right)
swap(a[left],a[right]);
}
if (left == right)
swap(a[left],key);
return left;
}
}
void QuickSort1(int* a, int left, int right)
{
if (left >= right)
return ;
int begin = left;
int end = right;
int div = _QuickSort1(a,begin,end);
QuickSort1(a,begin,div-1);
QuickSort1(a,div+1,end);
}
//快速排序 挖坑法
int _QuickSort2(int* a, int left, int right)// 快速排序 挖坑法
{
if (left < right)
{
int key = a[right];
while (left < right)
{
while (left < right&&a[left] <= key)
{
left++;
}
a[right] = a[left];
while (left < right&&a[right] >= key)
{
right--;
}
a[left] = a[right];
}if (left == right)
a[left] = key;
return left;
}
}
int QuickSort2(int* a, int left, int right)
{
if (left >= right)
return 0;
int begin = left;
int end = right;
int div = _QuickSort2(a, begin, end);
QuickSort2(a,begin,div-1);
QuickSort2(a,div+1,end);
}
//快速排序 前后指针法
int _QuickSort3(int* a, int left, int right)//快速排序 前后指针法
{
if (left < right)
{
int cur = left;
int prev = cur - 1;
while (cur < right)
{
if (a[cur] < a[right] && ++prev != cur)
swap(a[cur],a[prev]);
cur++;
}swap(a[right],a[++prev]);
return prev;
}
}
int QuickSort3(int* a, int left, int right)
{
if (left >= right)
return 0;
int begin = left;
int end = right;
int div = _QuickSort3(a,begin,end);
QuickSort3(a,begin,div-1);
QuickSort3(a,div+1,end);
}
//快速排序 三数取中法
//上面的代码思想都是直接拿序列的最后一个值作为枢轴，如果最后这个值刚好是整段序列最大或者最小的值，那么这次划分就是没意义的。
//所以当序列是正序或者逆序时，每次选到的枢轴都是没有起到划分的作用。快排的效率会极速退化。
//所以可以每次在选枢轴时，在序列的第一，中间，最后三个值里面选一个中间值出来作为枢轴，保证每次划分接近均等。
int _QuickSort5(int* a, int left, int right)//快速排序 三数取中法
{
int mid = left + (right - left) / 2;
if (a[left] > a[mid]) swap(a[left],a[mid]);
if (a[left] > a[right]) swap(a[left],a[right]);
if (a[mid] > a[right]) swap(a[mid], a[right]);
if (mid < right - 1)swap(a[mid], a[right - 1]);
if (left + 1 <= right - 2) //
{
int begin = left + 1;
int end = right - 2;
while (begin<end)
{
while (begin < end&&a[begin] < a[right - 1])
{
begin++;
}
while (begin < end&&a[end] > a[right - 1])
{
end++;
}
swap(a[begin], a[end]);
}
if (begin == end)
swap(a[begin],a[right-1]);
return begin;
}
return mid;
}
void QuickSort5(int *a, int left, int right)
{
assert(a);
if (left >= right)
return;
int mid = _QuickSort5(a,left,right);
QuickSort5(a,left,mid-1);
QuickSort5(a,mid+1,right);
}
//归并排序
//该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列
void Merge(int* a, int* b, int begin, int mid, int end)//归并排序
{
int i = begin, j = mid + 1, k=0;
while (i <= mid&&j <= end)
{
if (a[i] <= a[j])
{
b[k++] = a[i++];
}
else
b[k++] = a[j++];
}
while (i <= mid)
{
b[k++] = a[i++];
}
while (j <= end)
{
b[k++] = a[j++];
}
memcpy(a + begin, b, sizeof(int)*(end - begin + 1));
}
void _MergeSrot(int *a,int *b,int begin,int end)
{
if (begin < end)
{
int mid = begin + (end - begin) / 2;//先分组
_MergeSrot(a,b,begin,mid);
_MergeSrot(a,b,mid+1,end);
Merge(a,b,begin,mid,end); //最后一步合并
}
}
void MergeSort(int* a, int n)
{
int *b = new int[n];
_MergeSrot(a,b,0,n-1);
delete[] b;
}
// 7.冒泡排序 加优化
// 思路：从第一个数开始，两两比较，小的放前面，每轮找出一个最大的放到最后面。
void Bubblesort(int* a,int size)
{
assert(a);
int count = 0; //优化，如果有序的话，就没有继续比较的必要了
for(int i = 0 ; i < size-1 ; i++)
{
count=0;
for(int j=0;j<size-1-i;j++)//每次都从头开始
{
if(a[j] > a[j+1])
{
swap(a[j],a[j+1]);
count++;
}
}
if(count == 0) //如果当前没有比较，也就是说已经有序了，直接返回了。
return;
}
}
// 8.计数排序 稳定(相同元素的相对位置不变)
// 时间复杂度O(n+k) k是最大最小的差值
// 空间复杂度O(k) 也可以是O(n+k) 需要开辟一个跟原数组一样大的数组
// 适用于 数据集中且重复居多的情况比如{2，2，2，3，3，4，4，4，5}；知道最小的数和最大的数
// 数据越集中越节省空间，总的来说是一个用空间换取时间的排序
void CountSort(int* a, int n, int max,int min) //计数排序
{
int size = max - min + 1;
int *b = new int[size];
memset(b,0,sizeof(int)*size); //将b的值全赋为0
for (int i = 0; i < n; i++)
{
b[a[i]-min]++;
}
int k = 0;
for (int i = 0; i < size; i++)
{
while (b[i])
{
a[k++]=i+min;
b[i]--;
}
}
delete[] b;
return;
}
// 9.基数排序 稳定
// 时间复杂度O(d*n) d是最大位数 比如最大 123 是3位 n是元素个数
// 空间复杂度O(n+10) 开辟了原数组一般大的桶，和10大小的数组
// 思路：从个位依次开始排序，排到最高位就完成了。其中每轮排序会统计0~9上的个数(利用了计数排序)，建立右索引，并放入原数组。
int GetDigit(int key, int d)//d是位数 得到一个数从右到左某一位的数 比如123第三位是1
{
int a[] = {1,10,100};
return key/(a[d-1]);//先设置最大是三位数
}
void RadixSort(int* a, int begin, int end, int d)//d是最大位数 比如1234 位数是4
{
int count[10];//0~9
int* bucket = (int *)malloc((end-begin+1)*sizeof(int));//开辟桶空间
for (int i = 1; i <= d; i++)//从个位开始，十位...，依次排序。
{
//将数组 清零
for (int j = 0; j < 10; j++)
{
count[j] = 0;
}
//统计每个桶中的个数
for (int j = begin; j <= end; j++)
{
count[GetDigit(a[j],i)]++;
}
//此时记录每个桶的右边界索引，放数据进桶中便时是数据的索引数(第几个数)
for (int j = 1; j < 10; j++)
{
count[j] = count[j] + count[j - 1];
}
//将元素放入桶中
for (int j = end; j >= begin; j--)
{
int k = GetDigit(a[j],i);
bucket[count[k] - 1] = a[j];
count[k]--;
}
//将桶中元素拷贝回原数组
for (int j = begin; j <= end; j++)
{
a[j] = bucket[j];
}
}
free(bucket);
}
