算法2—八大常用排序算法（下）
1.直接选择排序
基本思想：
每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。
时间复杂度：O（n²）
void SelectSort(int* arr, int n)
{
for (int i = 0; i < n; i++)
{
int begin = i;
int end = n - 1;
int mini = i;
//找最小的
for (int j = i+1; j < n; j++)
{
if (arr[j] < arr[mini])
{
mini = j;
}
}
//找到了最小值，i和mini的位置进行交换
Swap(&arr[begin++], &arr[mini]);
}
}提高算法效率：寻找最大值和最小值，同时操作。
时间复杂度：O（n²）
void SelectSort_2(int* arr, int n)
{
int begin = 0;
int end = n - 1;
while ( begin < end )
{
int mini = begin;
int maxi = begin;
for (int i = begin; i <= end; i++)
{
if (arr[i] > arr[maxi])
{
maxi = i;
}
if (arr[i] < arr[mini])
{
mini = i;
}
}
if (maxi == begin)
{
maxi = mini;
}
Swap(&arr[mini], &arr[begin++]);
Swap(&arr[maxi], &arr[end--]);
}
}2.快速排序
2.1Hoare版本
快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法，其基本思想为：任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。
时间复杂度：O（n*logn）
int _QuickSort(int* arr, int left, int right)
{
int keyi = left;
++left;
while (left<=right)
{
while (arr[right] > arr[keyi] && left <= right )
{
right--;
}
//right找到比基准值小，或者刚好等于
while (arr[left] < arr[keyi] && left <= right )
{
left++;
};
//left找到比基准值大，或者刚好等于
if (left <= right)
{
Swap(&arr[left++], &arr[right--]);
}
}
Swap(&arr[keyi], &arr[right]);
return right;
}
void QuickSort(int* arr, int left, int right)
{
if (left >= right)
{
return;
}
int key = _QuickSort(arr, left, right);//找到基准值
//左子序列：[left,key-1]
QuickSort(arr,left,key-1);
//右子序列：[key+1,right]
QuickSort(arr,key+1,right);
}2.2挖坑法
思路：创建左右指针。
首先从右向左找出比基准值小的数据，找到后立即放入左边坑中，当前位置变为新的“坑”，然后从左向右找出比基准值大的数据，找到后立即放入右边坑中，当前位置变为新的“坑”，结束循环后将最开始存储的分界值放入当前“坑”中，返回当前“坑”下标。
int __QuickSort(int* arr, int left, int right)
{
int hole = left;
int key = arr[hole];
while (left < right)
{
while (left < right && arr[right] > key)
{
right--;
}
arr[hole] = arr[right];
hole = right;
while (left < right && arr[left] < key)
{
left++;
}
arr[hole] = arr[left];
hole = left;
}
arr[hole] = key;
return hole;
}
void QuickSort(int* arr, int left, int right)
{
if (left >= right)
{
return;
}
int key = __QuickSort(arr, left, right);//找到基准值
//左子序列：[left,key-1]
QuickSort(arr,left,key-1);
//右子序列：[key+1,right]
QuickSort(arr,key+1,right);
}2.3 lomuto前后指针
创建前后指针，从左往右找比基准值小的，进行交换，使得小的都排在基准值左边。
int ___QuickSort(int* arr, int left, int right)
{
int keyi = left;
int prev = left;
int cur = left + 1;
while (cur <= right)
{
if (arr[cur] < arr[keyi] && ++prev != cur)
{
Swap(&arr[cur], &arr[prev]);
}
cur++;
}
Swap(&arr[keyi], &arr[prev]);
return prev;
}
void QuickSort(int* arr, int left, int right)
{
if (left >= right)
{
return;
}
int key = __QuickSort(arr, left, right);//找到基准值
//左子序列：[left,key-1]
QuickSort(arr,left,key-1);
//右子序列：[key+1,right]
QuickSort(arr,key+1,right);
}2.4非递归版本—栈
void QuickSortNonR(int* arr, int left, int right)
{
ST st;
STInit(&st);
StackPush(&st, right);
StackPush(&st, left);
while (!StackEmpty(&st))
{
//取栈顶元素，取两次
int begin = StackTop(&st);
StackPop(&st);
int end = StackTop(&st);
StackPop(&st);
//找基准值
int prev = begin;
int cur = begin + 1;
int keyi = begin;
while (cur <= end)
{
if (arr[cur] <= arr[keyi] && prev++ != cur)
{
Swap(&arr[cur], &arr[prev]);
}
cur++;
}
Swap(&arr[keyi], &arr[prev]);
keyi = prev;
//根据基准值划分左右区间
//左区间：[begin,keyi-1]
//右区间：[keyi+1，end]
if ( keyi+1 < end )
{
StackPush(&st, end);
StackPush(&st, keyi + 1);
}
if (keyi-1 > begin)
{
StackPush(&st, keyi-1);
StackPush(&st, begin);
}
}
STDestroy(&st);
}3.归并排序
算法思想：归并排序是建立在归并操作上的一种有效的排序算法，该算法是采用分治法的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。
时间复杂度：O（n*logn）
void _MergeSort(int* arr,int left,int right,int* tmp)
{
if (left >= right)
{
return;
}
int mid = (left + right) / 2;
//[left,mid]
//[mid+1,right]
_MergeSort(arr, left, mid, tmp);
_MergeSort(arr, mid+1, right, tmp);
//合并
int begin1 = left;
int end1 = mid;
int begin2 = mid + 1;
int end2 = right;
int index = begin1;
while (begin1 <= end1 && begin2 <= end2)
{
if (arr[begin1] < arr[begin2])
{
tmp[index++] = arr[begin1++];
}
else
{
tmp[index++] = arr[begin2++];
}
}
//begin1越界或者begin2越界
while (begin1 <= end1)
{
tmp[index++] = arr[begin1++];
}
while (begin2 <= end2)
{
tmp[index++] = arr[begin2++];
}
//把tmp的数据拷贝的arr中
for (int i = left; i <= right; i++)
{
arr[i] = tmp[i];
}
}
void MergeSort(int* arr, int n)
{
int* tmp = (int*)malloc(sizeof(int) * n);
_MergeSort(arr,0,n-1,tmp);
free(tmp);
}4.非选择排序
4.1计数排序
计数排序又称为鸽巢原理，是对哈希直接定址法的变形应用。
- 统计相同元素出现次数
- 根据统计的结果将序列回收到原来的序列中
void CountSort(int* arr, int n)
{
//根据最大值和最小值确定数组大小
int max = arr[0];
int min = arr[0];
for (int i = 1; i < n; i++)
{
if (arr[i] > max)
{
max = arr[i];
}
if (arr[i] < min)
{
min = arr[i];
}
}
int* count = (int*)malloc(sizeof(int) * ((max - min) + 1));
if (count == NULL)
{
perror("malloc error");
exit(1);
}
memset(count,0,sizeof(int)*( (max - min) + 1));
//统计数组中每个数据出现的次数
for (int i = 0; i <= n; i++)
{
count[arr[i] - min]++;
}
//取count中的数据，往arr中放
int index = 0;
for (int i = 0; i < ((max - min) + 1); i++)
{
while (count[i]--)
{
arr[index++] = i + min;
}
}
}5.排序算法复杂度及稳定性分析
稳定性：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的。
