今天接到了秋招的第一个电话，是腾讯面试官的打来的，面试官问我最常用的排序，我直接说了快排，说完就后悔了，嗯，我太草率了，不同的场景使用不同的排序算法本身没有好坏之分。
记录这篇简书，一是为了之后不犯相同的错误，二是将排序算法分享给正在求职的小伙伴们。
（Ps:所有算法均自己测试通过没有bug,如果小伙伴们有疑问请随时留言提问~~~）
当面试官问上面我说的那个问题的时候要首先考虑清楚面试官要干什么？比如：
可以反问面试官：
- 有没有大量的重复值？-->计数排序
- 是否大部分数据距离他们 的正确位置很近？是否近乎有序？-->插入排序
- 是否数据的取值范围非常有限？比如学生成绩排序。-->计数排序
- 是否需要稳定？-->优先考虑归并
- 是否使用链表存储？-->链表归并排序或者链表快速排序（关于链表的排序近期会有更新）
- 数据的大小是否可以装载到内存中？-->外排序
/**
* 冒泡排序：
*
* 时间复杂度：
* O(n)^2
* 空间复杂度：
* O(1)
* 稳定性：
* 稳定
*
* 以升序情况下为例：
* 1.首先指针指向数组中的第一个元素，让当前元素和他后一个元素做比较，
* 如果比后一个元素大的话，交换两个元素的位置。
* 2.指针向后挪动一个单位，继续重复上面的的步骤，直到指针走到数组长度减一的位置，
* 那个此时数组中的最大值就是数组中的最后一个元素，
* 3.数组的长度减一，继续重复上面的动作，直到数组的长度为1的时候结束。
*
* 缺点：
* 可能在数组长度不到1的时候，序列就已经有序了，所以，
* 增加一个标志位，如果在发生交换，更改标志位，
* 一次排序后，判断标志位是否更改，如果没有更改代表排序已经完成
*/
void bubble_sort(int arr[], int len){
int flag = 1;
for (int i = 0;flag && i < len - 1; i++){
flag = 0;
for (int j = i; j < len-1-i; j++){
if (arr[j]>arr[j + 1]){
flag = 1;
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
/**
* 插入排序：
*
* 时间复杂度：
* O(n)^2
* 空间复杂度：
* O(1)
* 稳定性：
* 不稳定
*
* 是升序情况为例：
* 将数组分成有序和无序两部分，每次从无序的数组中取出一个元素插入到有序的那部分中
*
*/
void insert_sort(int data[], int len){
for (int i = 0; i < len - 1; i++){
int temp = data[i + 1];
int j = i;
while (j >= 0 && data[j]>temp){
data[j + 1] = data[j];
j--;
}
data[j + 1] = temp;
}
}
/**
* 选择排序：
*
* 时间复杂度：
* O(n)^2
* 空间复杂度：
* O(1)
* 稳定性：
* 不稳定
*
* 是升序情况为例：
* 它的工作原理是每一次从待排序的数据元素中选出最小（或最大）的一个元素，
* 存放在序列的起始位置，直到全部待排序的数据元素排完
*/
void select_sort(int data[], int len){
int min;
for (int i = 0; i < len-1; i++){
int min = i;
for (int j = i + 1; j < len; j++){
if (data[min]>data[j]){
min = j;
}
}
if (min != i){
int temp = data[i];
data[i] = data[min];
data[min] = temp;
}
}
}
/**
* 归并排序：
*
* 时间复杂度：
* O(n log n)
* 空间复杂度：
* O（n)
* 稳定性：
* 稳定
*
* 该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。
* 将已有序的子序列合并，得到完全有序的序列；
* 即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表
*/
void array_merge(int data[], int low, int mid, int high){
int len = high - low;
int *p = (int*)malloc(sizeof(int)*len);
int i = low, j = mid, k = 0;
while (i < mid&&j < high){
if (data[i] < data[j]){
p[k++] = data[i++];
}
else{
p[k++] = data[j++];
}
}
while (i < mid){
p[k++] = data[i++];
}
while (j < high){
p[k++] = data[j++];
}
for (int i = 0, j = low; i < k; i++){
data[j++] = p[i];
}
free(p);
}
void merge_sort(int data[], int low, int high){
if (NULL == data || low < 0 || high <= 0||low>=high){
return;
}
if (high - low == 1){
return;
}
int mid = (high - low) / 2 + low;
merge_sort(data, low, mid);
merge_sort(data, mid + 1, high);
array_merge(data, low, mid, high);
}
/**
*
* 快速排序：
*
* 时间复杂度：
* O(n log n)
* 空间复杂度：
* O（n)
* 稳定性：
* 不稳定
*
* 首先确定一个基准值，通过比较和交换，使得基准值左边的数字都比基准值小
* 基准值右边的数都比基准值大，然后以基准值为分割点，分成三部分，分别进行左递归和右递归进行排序。
*
*
* 缺点：
* 传统基准值的选定时每次参照顺序表的第一个元素作为基准值，
* 但是如果数组为有序的情况下，会大大降低排序效率，退化成冒泡排序时间复杂度升为O(n^2)
* 解决方案就是三数取中。
*
*
* 优化1：
* 当待排序序列的长度分割到一定大小后，使用插入排序
* 原因：
* 对于很小和部分有序的数组，快排不如插排好。
* 当待排序序列的长度分割到一定大小后，继续分割的效率比插入排序要差，此时可以使用插排而不是快排。
*
* 优化2：
* 在一次分割结束后，可以把与Key相等的元素聚在一起，继续下次分割时，不用再对与key相等元素分割
* 在一次划分后，把与key相等的元素聚在一起，能减少迭代次数，效率会提高不少
* 具体过程：在处理过程中，会有两个步骤
* 第一步，在划分过程中，把与key相等元素放入数组的两端
* 第二步，划分结束后，把与key相等的元素移到枢轴周围
*/
void swap(int *a, int *b){
int temp = *a;
*a = *b;
*b = temp;
}
//三数取中：先找到一个最大值放到data[len-1]的位置，
//之后mid值通过data[low]和data[mid]确定
int midAndSwap(int data[], int low, int high){
if (NULL == data || low < 0 || high <= 0){
return 0;
}
int mid = (high - low) / 2 + low;
if (data[low]>data[high - 1]){
swap(&data[low], &data[high - 1]);
}
if (data[mid] > data[high - 1]){
swap(&data[mid], &data[high - 1]);
}
if (data[low] < data[mid]){
swap(&data[low], &data[mid]);
}
return data[low];
}
void insertSort(int data[], int len){
for (int i = 0; i < len - 1; i++){
int temp = data[i + 1];
int j = i;
while (j >= 0 && data[j]>temp){
data[j + 1] = data[j];
j--;
}
data[j + 1] = temp;
}
}
void quickSort(int data[], int low, int high){
//转换成插入排序数组的长度为（5<len<15）
if ((high - low) < 2){
insertSort(data + low, high - low);
return;
}
int left = low;
int right = high - 1;
int leftCopy = left;
int rightCopy = right;
int key = midAndSwap(data, low, high);
while (left < right){
for (; left < high&&data[left] <= key; left++){
if (key == data[left]){
swap(&data[left], &data[leftCopy]);
leftCopy++;
}
}
for (; right >= left&&data[right] >= key; right--){
if (key == data[right]){
swap(&data[right], &data[rightCopy]);
rightCopy--;
}
}
if (left < right){
int temp = data[left];
data[left] = data[right];
data[right] = temp;
}
}
//将枢纽元素移动到中间位置
left = right;
while (leftCopy - low){
swap(&data[--leftCopy], &data[left--]);
}
if (right - left){
right++;
}
while (high - 1 - rightCopy){
swap(&data[++rightCopy], &data[right++]);
}
quickSort(data, low, left + 1);
quickSort(data, right, high);
}
/**
* 堆排序
*
* 时间复杂度：
* O(n log n)
* 空间复杂度：
* O（1)
* 稳定性：
* 不稳定
*
* 堆排序的基本思想是：将待排序序列构造成一个小根堆，此时，整个序列的最小值就是堆顶的根节点。
* 将其与末尾元素进行交换，此时末尾就为最小值。
* 然后将剩余n-1个元素重新构造成一个堆，这样会得到n个元素的次小值。
* 如此反复执行，便能得到一个有序序列了。
*
* 参考博客：https://www.cnblogs.com/chengxiao/p/6129630.html
*/
void heap_sort(int data[], int len){
if (data == NULL || len <= 0){
}
int pa, tag , end = len;
//end-1解释： 在数组中只剩下一个元素的时候不用比较
while (end - 1){
tag = 1;
while (tag){
pa = end / 2;
tag = 0;
while (pa){
if (data[pa] < data[2 * pa]){
swap(&data[pa], &data[2 * pa]);
tag = 1;
}
if (2 * pa + 1 <= end&&data[pa] < data[2 * pa + 1]){
swap(&data[pa], &data[2 * pa + 1]);
tag = 1;
}
pa--;
}
}
swap(&data[1], &data[end--]);
}
}
/**
* 计数排序：
*
* 时间复杂度：
* O(n)
* 空间复杂度：
* O（1)
* 稳定性：
* 不稳定
*
* 适合数据特别集中的情况。
* 这里以升序，且数据范围在0-100之间的数
* 根据获得的数据表的范围，分割成不同的100个桶，
* 然后直接统计数据在桶上的频次，然后顺序遍历桶就可以得到已经排好序的数据表。
*
*/
void count_sort(int data[], int len){
if (NULL == data || len <= 0){
return;
}
int table[100] = { 0 };
for (int i = 0; i < len; i++){
table[data[i]]++;
}
int index = 0;
for (int i = 0; i < 100; i++){
while (table[i]){
data[index++] = i;
table[i]--;
}
}
}
/*
希尔排序：
时间复杂度：
O(n)
空间复杂度：
O(1)
稳定性：
不稳定
比较相隔较远距离（称为增量）的数，使得数移动时能跨过多个元素，
则进行一次比较就可能消除多个元素交换。
算法先将要排序的一组数按某个增量d分成若干组，每组中记录的下标相差d.对每组中全部元素进行排序，
然后再用一个较小的增量对它进行，在每组中再进行排序。
当增量减到1时，整个要排序的数被分成一组，排序完成。
*/
/**
* 外排序
*
* 基本要点：
* 外部排序顾名思义是对外部存储空间中数据的排序，那为什么不能像选择排序、插入排序、快速排序那样也直接进行排序呢？
* 原因是外部存储的数据量可能是非常大的，而计算机的内存大小要远远小于外存，计算机一下子读不了那么多数据，
* 无法一次性对它们进行排序，这就是外部排序产生的原因。
* 基本思想：
* 1. 我们这里借助归并排序的思想
* 假设我的一个文件中有10000个数据，而我的内存每次只能读2000个数据，那我先对文件预处理一下，将原文件切割成5个小文件，
* 每个文件中有2000个有序数据（在读入内存2000个数据后，对数据排序后再写入到新文件中）。
* 2. 然后我们开始进行文件合并（这里采用2-路归并）。先分别打开两个文件，分别读取文件的第一行数据，
* 把数据较小的写入到一个新文件中，然后把数据较小的文件再往下读一行，直到两个文件中的数据全部有序地写到新文件中为止，
* 这样原先5个2000个数据的文件变为2个4000个数据和1个2000个数据的文件。
* 3. 重复步骤2，再次合并变为1个8000个数据和1个2000个数据的文件，
* 再次合并变为1个10000个数据的文件。排序完成，原先有10000个数据的文件变得有序。
*
*/
网友评论