1. 快速排序
快速排序就是挖坑再填坑。一般我取最左边的那个数作为基准数temp，然后从右往左遍历数组直到找到一个数小于temp，将这个数挖出，填在基准数所在的位置，然后再从左往右找到一个大于temp，再交换。就这样不断的重复，直到排序完成。
int quickSort(int s[],int _left,int _right)
{
if (_left < _right)
{
int l = _left, r = _right, temp = s[_left];
while (l < r)
{
while (l < r&&s[r] >= temp)
r--;
if (l < r)
s[l++] = s[r];
while (l < r&&s[l] < temp)
l++;
if (l < r)
s[r--] = s[l];
}
s[l] = temp;
quickSort(s, _left, l - 1);
quickSort(s, l + 1, _right);
}
}
2. 堆排序
堆排序的关键是在建堆和调整堆。
其实整个堆排序过程中, 我们只需重复做两件事：
- 建堆(初始化+调整堆, 时间复杂度为O(n));
- 拿堆的根节点和最后一个节点交换(siftdown, 时间复杂度为O(n*log n) )
下面通过一组数据说明堆排序的方法：
9, 79, 46, 30, 58, 49
-
将排序的数视为完全二叉树（按层次进行排序）
初始化 -
判断完全二叉树的最后一个非叶子节点的左右子树是否小于它，如果小于就进行调整。最后一个节点的索引为数组长度len-1，那么最后一个非叶子节点的索引应该是为(len-1)/2.也就是从索引为2的节点开始，如果其子节点的值大于其本身的值。则把他和较大子节点进行交换，即将索引2处节点和索引5处元素交换。交换后的结果如图
第一次比较 - 再向前处理前一个节点，即节点1，此时79>30&&79>58，无需交换
-
再次向前处理前一个节点，即节点0，此时9<79&&9<49，所以需要进行交换，将节点0与它的后一个节点进行交换，也就是节点1，因为79>49
第二次交换 -
如果某个节点与它的子节点交换后，它的子节点也有子节点，那么系统还需要再次对该子节点进行判断。如上图因为1处，3处，4处中，1处的值大于3,4出的值，所以还需交换。
调整子节点的子节点
void adjust(int arr[], int len, int index)
{
int left = 2*index + 1;
int right = 2*index + 2;
int maxIdx = index;
if(left<len && arr[left] > arr[maxIdx]) maxIdx = left;
if(right<len && arr[right] > arr[maxIdx]) maxIdx = right; // maxIdx是3个数中最大数的下标
if(maxIdx != index) // 如果maxIdx的值有更新
{
swap(arr[maxIdx], arr[index]);
adjust(arr, len, maxIdx); // 递归调整其他不满足堆性质的部分
}
}
void heapSort(int arr[], int size)
{
for(int i=size/2 - 1; i >= 0; i--) // 对每一个非叶结点进行堆调整(从最后一个非叶结点开始)
{
adjust(arr, size, i);
}
for(int i = size - 1; i >= 1; i--)
{
swap(arr[0], arr[i]); // 将当前最大的放置到数组末尾
adjust(arr, i, 0); // 将未完成排序的部分继续进行堆排序
}
}
int main()
{
int array[8] = {8, 1, 14, 3, 21, 5, 7, 10};
heapSort(array, 8);
for(auto it: array)
{
cout<<it<<endl;
}
return 0;
}
3. 基数排序
它就是桶排序的拓展，它将整数的各个位置从大到小进行排序，先对个位数进行排序，然后对十位数...，位数小的数前面补0.
排序图示
基数排序的流程
- 先获得数组的最大值计算出最大指数
- 从指数1开始根据位数对数组进行排序
- 对数组按照指数进行排序
int getMax(int a[], int n)
{
int max=a[0];
for (int i = 0; i < n; i++)
{
if (a[i]>max)
max = a[i];
}
return max;
}
void countSort(int a[], int n, int exp)
{
vector<int> output(10);
int i, buckets[10] = { 0 };
//将数据出现的次数存储在buckets[]中
for (int i = 0; i < n; i++)
buckets[(a[i] / exp) % 10]++;
//更改buckets[]的值，对应output的位置
for (int i = 0; i < n; i++)
buckets[i] += buckets[i - 1];
//将数据存储到临时数组中
for (int i = n - 1; i >= 0; i--)
{
output[buckets[(a[i] / exp) % 10] - 1] = a[i];
buckets[(a[i] / exp) % 10]--;
}
// 将排序好的数据赋值给a[]
for (i = 0; i < n; i++)
a[i] = output[i];
}
void radixSort(int a[], int n){
int exp;
int max = getMax(a, n);
for (exp = 1; max / exp > 0; exp *= 10)
countSort(a, n, exp);
}
4. 归并排序
归并排序的基本思想是将若干个序列进行两两归并，直至所有待排序记录都在一个有序序列为止。
归并排序
void Merge(int arr[], int reg[], int start, int end) {
if (start >= end)return;
int len = end - start, mid = (len >> 1) + start;
//分成两部分
int start1 = start, end1 = mid;
int start2 = mid + 1, end2 = end;
//然后合并
Merge(arr, reg, start1, end1);
Merge(arr, reg, start2, end2);
int k = start;
//两个序列一一比较,哪的序列的元素小就放进reg序列里面,然后位置+1再与另一个序列原来位置的元素比较
//如此反复,可以把两个有序的序列合并成一个有序的序列
while (start1 <= end1 && start2 <= end2)
reg[k++] = arr[start1] < arr[start2] ? arr[start1++] : arr[start2++];
//然后这里是分情况,如果arr2序列的已经全部都放进reg序列了然后跳出了循环
//那就表示arr序列还有更大的元素(一个或多个)没有放进reg序列,所以这一步就是接着放
while (start1 <= end1)
reg[k++] = arr[start1++];
//这一步和上面一样
while (start2 <= end2)
reg[k++] = arr[start2++];
//把已经有序的reg序列放回arr序列中
for (k = start; k <= end; k++)
arr[k] = reg[k];
}
void MergeSort(int arr[], const int len) {
//创建一个同样长度的序列,用于临时存放
int reg[len];
Merge(arr, reg, 0, len - 1);
}
