排序总览

2024-05-09 22:18
文章标签 排序 总览

本文主要是介绍排序总览，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

排序是出镜率最高的面试题，基本上没有之一


一、就排序说排序

这一环节的目的，一方面是完全熟悉常用常考的排序，另一方面是对排序所涉及的相关的知识，如时间复杂度的感觉到理解、不同的数据结构、不同的算法思路、排序解决的问题、排序在实际问题中的用途，建立一个更全面的体系，毕竟不论是面试还是实际工作，所面对的问题远远不会是仅是会写排序。

1.0、排序本身都有哪些排序：

1、原地比较排序：和线性排序实质区别是，原地比较排序的时间复杂度不是O(N)，在理论上最高只能做到O(N*logN)，而线性排序达到O(N)线性复杂度

按核心思路分为：

1.1、基于选择的：不断选出特大/小值。

冒泡排序：稳定、接近O(N^2)，从头到尾共N趟，发现有更大/小就交换

快速排序：不稳定(因为会劈开)、平均/可认为O(N*logN)、原始数据越有序则越慢(因为导致大量数据交换)最慢O(N^2)、最好情况也是O(N*logN)，典型的分治思想的运用，选一个标杆值，然后把其他数据按标杆值分为两部分，就这样不断细分下去，最终实现全部有序。

  快排的分治思路非常重要，不仅排序用到，诸如找第K大的数这样的使用分治解决的问题同样会用到

冒泡排序：

/**  buddle sort* */
void buddle_sort (int *data, int size) {for (int i = 0; i < size; i++) {for (int j = i; j < size; j++) {if (data[j] < data[i]) {int tmp = data[j];data[j] = data[i];data[i] = tmp;}}}
}

快速排序：

/**  quick sort* */
int partition (int *data, int start, int end) {if (start < end) {int flagval = data[end];int i = start, j = start;for (; i < end; ++i) {if (data[i] < flagval) {int tmp = data[i];data[i] = data[j];data[j++] = tmp;}}int tmp = data[j];data[j] = flagval;data[end] = tmp;return j;} else {return -1;}
}void qsort_unrecursion (int *data, int size) {int part = partition(data, 0, size - 1);std::stack<int> stk;stk.push(0);stk.push(part - 1);stk.push(part + 1);stk.push(size - 1);while (!stk.empty()) {int end = stk.top();stk.pop();int start = stk.top();stk.pop();if (start < end) {int part = partition(data, start, end);if (part > 0) {stk.push(start);stk.push(part - 1);stk.push(part + 1);stk.push(end);}}}
}


1.2、 基于交换的：

选择排序：稳定、接近于O(N^2)，从头到尾共N趟，每一趟找出第i个索引到尾部的最大/小值

堆排序：不稳定、接近于O(N*logN)(完全二叉树，无最好最坏平均之分)，每趟均二叉的找出剩余数据的最大/小者作为堆顶，直到全部处理完毕

堆在海量数据面试题中常常被用到，典型为topk、中位数、第K大。实际应用中也经常用于维护满足"可能定长的、且动态可变"性质的业务结构数据。

选择排序：

/**  select sort* */
void select_sort (int *data, int size) {for (int i = 0; i < size; i++) {int min = i;for (int j = i; j < size; j++) {if (data[min] > data[j]) {min = j;}}int tmp = data[i];data[i] = data[min];data[min] = tmp;}
}

堆排序： 

template<class T> class Heap {T *data;int size;public:Heap (T *_data, int _size):size(_size) {data = new T[_size + 1];for (int i = 1; i <= size; i++) {data[i] = _data[i - 1];}for (int i = size/2; i >= 1; --i) {adjust(i, size);}}~Heap () {if (data) {delete []data;}size = 0;}void adjust (int idx, int sz) {if (idx <= sz/2) {int l = idx * 2, r = idx * 2 + 1;int minidx = idx;if (l < sz && data[minidx] < data[l]) {minidx = l;}if (r < sz && data[minidx] < data[r]) {minidx = r;}if (idx != minidx) {T tmp = data[idx];data[idx] = data[minidx];data[minidx] = tmp;adjust(minidx, sz);}}}T gettop () {return data[1];}void settop (T val) {data[1] = val;for (int i = size; i >= 1; i--) {adjust(i, size);}}void sort () {for (int i = size; i >= 1; i--) {T min = data[1];data[1] = data[i];data[i] = min;adjust(1, i - 1);}}void show () {for (int i = 1; i <= size; i++) {std::cout << data[i] << ",\t";}std::cout << std::endl;}
};void heap_sort (int *data, int size) {Heap<int> hp(data, size);hp.sort();hp.show();
}

1.3、基于插入的：

插入排序：稳定、时间复杂度O(N^2)，相比冒泡和选择，相对难一些：

排序方式为，每个数据在其前面的数据找比他大/小的，即所谓的插入位置，在找到之前将做数据整体移位，

如原数据为1、2、3、100、101、102、103、4

则对于4的插入排序趟，找到合适的插入位置3之后的100过程中，它前面的103到100会在遍历过程中依次向前移位，直到找到3，将4插入在原先100的位置。

明显可见如果原始数据已经比较有序，那么插入排序进行的越快。如果原始数据已经完全有序，插入排序的时间复杂度为O(N)，反之则越慢，而且有大量的数据比较和交换的工作。

针对插入排序大量的数据比较工作的问题，一个常见的改进是，利用插入排序的"待排序数据之前的数据已经有序"的特点，不通过挨个比较，而是通过二分查找的方式找到待排序数据应该插入的位置，如上面的4，通过对1到103的数据进行二分查找找到应该插入的位置100；这样可大幅度减少数据比较，但仍然需要进行交换，依然是非常低效的。


所以插入排序往往用于链表，这也是链表排序面试题的解决方式之一(链表的原地排序，主要适合基于插入的和归并排序式的)，链表插入排序的核心思想是分治，初始将一个元素(往往是第一个元素)作为"已排序链表"，其他的元素作为"未排序链表"，然后把"未排序链表"的元素依次在"已排序链表"里寻找按顺序的插入点，直到"未排序链表"的元素都插入到了"已排序链表"。

对于插入排序，链表形式之所以合适就是因为不再大量的进行数据交换，而是仅修改指针的指向。

希尔排序：不稳定、平均时间复杂度被认为接近O(N^1.3)；希尔排序是"渐进式插入排序"的方式，针对插入排序适合数据越有序越快的特性，希尔排序不断用较少的排序次数，实现整个数据的较大程度有序；

希尔排序重在理解其其发明目的，是处于什么原因，对原始插入排序做的什么改进；

方式是，按由大逐渐到小的"步长"，把数据按照步长的对应数据达到有序，比如总数为10，步长初始为5，那么首先保证0和5、1和6、.......4和9的有序，然后步长减少为2，保证0和2、0和2和4、0和2和4和8的有序，然后步长为1，变成插入排序，由于前面弄的数据已经相对比较有序了，所以现在做插入排序就比较快了；

二分查找优化的插入排序、链表式插入排序、希尔排序都是堆插入排序的优化改进。

二分查找优化的插入排序：

/**  insert sort* */
int binary_search (int *data, int cur, int start, int end) {while (start <= end) {int mid = (start + end)/2;if (data[mid] < cur) {start = mid + 1;} else if (data[mid] > cur) {end = mid - 1;} else {return mid + 1;}}return start;
}void insert_sort (int *data, int size) {for (int i = 1; i < size; ++i) {int cur = data[i], j = binary_search(data, cur, 0, i - 1);if (j >= 0) {for (int k = i; k > j; --k) {data[k] = data[k - 1];}data[j] = cur;}}
}


链表式插入排序： 
template<class T> struct Node {T val;Node<T> *next;Node (T _val):val(_val), next(nullptr) {}
};template<class T> class List {Node<T> *root;public:List (T *data, int size):root(nullptr) {for (int i = 0; i < size; i++) {if (!root) {root = new Node<T>(data[i]);} else {Node<T> *newnode = new Node<T>(data[i]);newnode->next = root->next;root->next = newnode;}}}~List () {if (root) {while (root) {Node<T> *next = root->next;delete root;root = next;}root = nullptr;}}void sort () {Node<T> *sorted = root, *unsorted = root->next;sorted->next = nullptr;while (unsorted) {Node<T> *p = sorted, *prev = sorted, *q = unsorted;for (; p && q->val >= p->val; p = p->next) {prev = p;}Node<T> *next = q->next;unsorted = next;if (p == sorted) {q->next = sorted;sorted = q;} else {q->next = p;prev->next = q;}}root = sorted;}void show () {Node<T> *cur = root;while (cur) {std::cout << cur->val << ",\t";cur = cur->next;}std::cout << std::endl;}
};void insert_list_sort (int *data, int size) {List<int> list(data, size);list.show();list.sort();list.show();
}

希尔排序： 

void shell_sort (int *data, int size) {for (int i = size/2; i > 0; i /= 2) {for (int j = i; j < size; j++) {int cur = data[j];int k = j;while (k >= 0 && cur <= data[k - i]) {data[k] = data[k - i];k -= i;}if (k < 0) {data[k + i] = cur;} else {data[k] = cur;}}}
}

1.4、归并排序：

归并排序从排序手段上，本身并没有什么新内容，重点在于思路：将原始数据分为不断的K分(K由2-M，M < N)，当数据被分割为小于K时，做每K路的合并，并对合并后的继续做K路的合并，直到都合并完成。K路归并排序则为O(N * logN / logK)。常用的是2路归并排序，即O(N*logN)。

如数据总量为10，首先分为两个大小分别为5的部分，然后再分为两个大小为2、两个大小为3的部分，然后分成8个大小为1、2个为2的部分，这时进行merge，merge的实现自定义。

归并排序是对数复杂度排序的终极排序方法。它是稳定的、时间复杂度也稳定为O(N*logN)的。

为了实现O(N*logN)的时间复杂度，归并排序事实上需要少量(<= N)多次的空间复杂度，即merge时用线性比较的方式，将结果写入临时额外空间，再更新原数据对应部分。这个很多文章没有明说，或者用隐晦的方式实现，表面看起来空间复杂度是O(1)。


归并排序重在思想，它是更复杂的问题，如海量数据中的各种问题中的一种重要解决思路，包括外部排序本身就是归并排序的思想出发点。

归并排序：

void sort (int *data, int st1, int ed1, int st2, int ed2) {int *tmp = new int[ed2 - st1 + 1];int start = st1;int i = 0;while (st1 <= ed1 && st2 <= ed2) {if (data[st1] < data[st2]) {tmp[i++] = data[st1++];} else {tmp[i++] = data[st2++];}}while (st1 <= ed1) {tmp[i++] = data[st1++];}while (st2 <= ed2) {tmp[i++] = data[st2++];}for (int idx = 0; idx < i; idx++) {data[start + idx] = tmp[idx];}delete []tmp;
}void merge_sort (int *data, int start, int end) {if (start < end) {int mid = (start + end)/2;merge_sort(data, start, mid);merge_sort(data, mid + 1, end);sort(data, start, mid, mid + 1, end);}
}



1.5、总结：

1、日常：不要求稳定，快排，因为速度最快；要求稳定时建议用归并；注意堆排序的使用；

2、堆排序的妙用、快排的分治的思想、分块再归并的思路，是排序的最重要需要理解和收获的内容；要作为解决更复杂问题的常规武器；

3、要注意链表的排序，链表排序除插入方式外，最适合的就是归并方式，典型题就是"合并两个有序链表"，如果可以使用额外空间，则归并排序是最佳方式；


2、线性排序：

数据总量为N，能保证也用O(N)的时间复杂度完成的排序。但往往都是有限制条件或适用场景。


1、计数排序：仅适用整数，必须明确最大值，最好从0开始。需要O(2 * N)的额外空间。

计数排序思路是：在明确所排序数字范围为0-N后，创建个数为N的数组并累计每个数字出现次数，进而得到每个数字出现的座次，如0出现2次，1出现3次，则0的座次为0-1，1的座次为2-4，以此类推得到全部数字的座次，然后是一个技巧，从后向前逆序遍历，将原始数据根据其座次，塞入结果数组；

缺点：当范围很大时，也需要一个巨大的O(range)的额外空间

计数排序：

/**  counter sort, range is 0-99* */
void countersort (int *data, int size, int max) {int range[100] = {0}, result[100];for (int i = 0; i < size; i++) {range[data[i]] += 1;}for (int i = 1; i < max; i++) {range[i] += range[i - 1];}for (int i = size - 1; i >= 0; i--) {if (range[data[i]]) {result[range[data[i]] - 1] = data[i];--range[data[i]];}}for (int i = 0; i < size; i++) {data[i] = result[i];}
}


2、桶排序：

桶排序思路：同样需要明确最大值，然后根据数值范围，再创建一个个的小范围，如数值范围为0-100，再创建0-9、10-19、......90-99的10个小范围，每个小范围称之为一个桶，原始数据根据大小落在对应的桶中，这样首先实现了数据的按范围有序，然后每个桶内数据再排序，最终将全部桶按顺序输出就是排序结果。

另类的归并排序，在海量数据问题中很有效，比如找第K大、中位数、topk等。

缺点：和计数排序一样，当范围很大时，需要一个巨大的O(range)的额外空间

桶排序：

class Bucket {std::vector<int> *buckets;public:Bucket (int *data, int size, int max, int base) {buckets = new std::vector<int>[max/base];for (int i = 0; i < size; i++) {int cur = data[i];int idx = cur/base;buckets[idx].push_back(cur);}sort(max/base);}~Bucket () {delete []buckets;}void sort (int num) {for (int i = 0; i < num; i++) {std::sort(buckets[i].begin(), buckets[i].end());}for (int i = 0; i < num; i++) {for (auto j: buckets[i]) {std::cout << j << "\t";}std::cout << std::endl;}}
};

3、基数排序：基数排序是一个广义维度思路的排序方式。基数的意思是，以什么指标作为排序依据。

在用于正整数排序时，排序指标是：每一个十进制整数的末位数大小，如：

1、100、105、5000、309

第1次比较末位数：排序结果为100、5000、1、105、309

第2次比较末位数：排序结果为100、5000、1、105、309

第3次比较末位数：排序结果为1、100、105、309、5000

第4次比较末位数：排序结果为1、100、105、309、5000


每次末位数的比较的排序方式随意，图简单直接用计数排序，0-9的数字范围只需要10个int的额外空间，时间复杂度O(N)

基数排序的空间复杂度为O(N + 10)相当于O(N)，时间复杂度大致为O(最大数字位数 * N * 2)，相当于O(N)O()

不同于计数排序和桶排序必须知道最大值确切范围，整数的基数排序只需知道最大值的位数


举一反三的思考，基数排序更大的意义在于通过不同的基数定义，进行不同的排序，如：

上亿个int32整数中找第K大/中位数。


原地比较排序中，

可以由快排的分治思想做，但快排会破坏原始数据；

可以由K大小的大顶堆实现，时间复杂度N*logN空间复杂度O(K)相当于没有；


线性排序中，计数排序也可以实现，比较有意思的解决方式是：

1、桶排序：分为若干桶，O(N)的插入不同的桶，插入后可发现每个桶内数据大小，则可定位第K大、中位数落在哪个桶的哪个位置，

然后对那个桶单独进行排序，取到那个位置的数据，使用额外空间可认为O(N)，时间复杂度可认为O(N)

2、基数排序：非上面的直接基数排序，而是同时借鉴直接基数排序和通排序，改排序指标即基数为每个数除以65535的余数，

这样对于int32的整数，会有最多65536个结果，即0-65535、65536-65536*2、...这样，

创建数组个数为65536，遍历一次数据，每个成员统计落到本区间数字的个数

这样，遍历一次后，同样可以根据每个区间的个数，判断出第K大/中位数在哪个区间及其位置，

然后再次遍历原始数据，专门找出落在对应区间的数据，进而找到该数据。

空间复杂度大幅度降低为O(65535)，因为每个区间仅仅计数，这点区别于桶排序方式，时间复杂度O(N * 2)相当于O(N)


当K比较大，比如上亿数找中位数时，基数排序的优势就体现出来了，相比其他任何方式，空间相对小速度相对快


基数排序：

int get_max_bit_num (int max) {int num = 0;while (max) {++num;max /= 10;}return num;
}void radixsort (int *data, int size, int max) {int maxbit = get_max_bit_num(max), base = 1;int range[10] = {0};int result[size];for (int i = 0; i < maxbit; i++) {for (int j = 0; j < 10; j++) {range[j] = 0;}for (int j = 0; j < size; j++) {int lastbit = (data[j]/(base)) % 10;++range[lastbit];}for (int j = 1; j < 10; j++) {range[j] += range[j - 1];}for (int j = size - 1; j >= 0; j--) {result[range[(data[j]/(base)) % 10] - 1] = data[j];--range[(data[j]/(base)) % 10];}for (int j = 0; j < size; j++) {data[j] = result[j];}base *= 10;}
}


二、更广义的排序：

1、hash族的bitmap，也是一个排序利器，需要的额外空间还更小，同样需要预先知道最大值，不过最好非负整数，并且最好不要重复；

限制条件较多，所以只在某些条件下适用。

时间复杂度O(N * 2)相当于O(N)，O(N/32 + 1)的额外空间，亮点是空间复杂度降低，对于不是特别巨大的海量数据有效。


bitmap排序：

class Bitmap {                                                                             int *data;                                                                             public:                                                                                    Bitmap (int max) {                                                                     data = new int[max/32 + 1];                                                        }                                                                                      ~Bitmap () {                                                                           delete []data;                                                                     }                                                                                      void Set (int d) {                                                                     data[d / 32] |= (1 << (d % 32));                                                   }                                                                                      void Traverse (int max) {                                                              for (int i = 0; i < max/32 + 1; i++) {                                             for (int j = 0; j < 32; j++) {                                                 if (data[i] & (1 << j)) {                                                  std::cout << i * 32 + j << " ";                                        }                                                                          }                                                                              }                                                                                  std::cout << std::endl;                                                            }                                                                                      
};

2、可排序的数据结构

对于实际的有序数据存储，肯定不是一个已知数组，而是一个数据结构，能够动态的增加/更新、删除成员，同时保持有序性，

排序的用途，最终归结在"可随时快速的增删查改"


对于可排序的数据结构，分为两大类：

1、树族：无翻转规则的二叉排序树、按翻转规则的二叉排序树、按分裂规则的多叉排序树

1.1、无翻转规则的二叉排序树：无实际用途

1.2、按翻转规则的二叉排序树：典型为AVL树、红黑树，其中红黑树用于标准库的map

对于这一类，明确为什么要翻转规则即可。不翻转放任自流，就像第一种，那么增删查改时间复杂度无法控制，极端情况下退化为有序链表

AVL的翻转较简单，任何一个节点底下的左右子树高度差不可超过1，超过1就翻转。所以AVL树的增删查改的时间复杂度肯定是O(logN)，

但缺点是总会引起翻转；而红黑树则一定程度上放宽了高度差要求，减少了翻转次数，增删查改的时间复杂度可认为也是O(logN)。

1.3、按分裂规则的多叉排序树：B族树，典型的被用于mysql

2、链表族：目前所了解的只有跳表

见跳表

这篇关于排序总览的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/974651。

相关文章

【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

前言：快速排序的实现最重要的是找基准值，下面让我们来了解如何实现找基准值 基准值的注释：在快排的过程中，每一次我们要取一个元素作为枢纽值，以这个数字来将序列划分为两部分。 在此我们采用三数取中法，也就是取左端、中间、右端三个数，然后进行排序，将中间数作为枢纽值。 快速排序实现主框架： //快速排序 void QuickSort(int* arr, int left, int rig
阅读更多...
usaco 1.3 Mixing Milk (结构体排序 qsort) and hdu 2020(sort)

usaco 1.3 Mixing Milk (结构体排序 qsort) and hdu 2020(sort)

到了这题学会了结构体排序 于是回去修改了 1.2 milking cows 的算法~ 结构体排序核心： 1.结构体定义 struct Milk{int price;int milks;}milk[5000]; 2.自定义的比较函数，若返回值为正，qsort 函数判定a>b ；为负，a<b；为0，a==b； int milkcmp(const void *va,c
阅读更多...
hdu 1285（拓扑排序）

hdu 1285（拓扑排序）

题意： 给各个队间的胜负关系，让排名次，名词相同按从小到大排。 解析： 拓扑排序是应用于有向无回路图(Direct Acyclic Graph,简称DAG)上的一种排序方式，对一个有向无回路图进行拓扑排序后，所有的顶点形成一个序列，对所有边(u,v)，满足u 在v 的前面。该序列说明了顶点表示的事件或状态发生的整体顺序。比较经典的是在工程活动上，某些工程完成后，另一些工程才能继续，此时
阅读更多...
《数据结构（C语言版）第二版》第八章-排序（8.3-交换排序、8.4-选择排序）

《数据结构（C语言版）第二版》第八章-排序（8.3-交换排序、8.4-选择排序）

8.3 交换排序 8.3.1 冒泡排序 【算法特点】 (1) 稳定排序。 (2) 可用于链式存储结构。 (3) 移动记录次数较多，算法平均时间性能比直接插入排序差。当初始记录无序，n较大时， 此算法不宜采用。 #include <stdio.h>#include <stdlib.h>#define MAXSIZE 26typedef int KeyType;typedef char In
阅读更多...
【软考】希尔排序算法分析

【软考】希尔排序算法分析

目录 1. c代码2. 运行截图3. 运行解析 1. c代码 #include <stdio.h>#include <stdlib.h> void shellSort(int data[], int n){// 划分的数组，例如8个数则为[4, 2, 1]int *delta;int k;// i控制delta的轮次int i;// 临时变量，换值int temp;in
阅读更多...
学习记录：js算法（二十八）：删除排序链表中的重复元素、删除排序链表中的重复元素II

学习记录：js算法（二十八）：删除排序链表中的重复元素、删除排序链表中的重复元素II

文章目录 删除排序链表中的重复元素我的思路解法一：循环解法二：递归 网上思路 删除排序链表中的重复元素 II我的思路网上思路 总结 删除排序链表中的重复元素 给定一个已排序的链表的头 head ， 删除所有重复的元素，使每个元素只出现一次 。返回 已排序的链表 。 图一 图二 示例 1：（图一）输入：head = [1,1,2]输出：[1,2]示例 2：（图
阅读更多...
鸡尾酒排序算法

鸡尾酒排序算法

目录 引言 一、概念 二、算法思想 三、图例解释 1.采用冒泡排序：   2.采用鸡尾酒排序：  3.对比总结 四、算法实现  1.代码实现  2.运行结果 3.代码解释   五、总结 引言 鸡尾酒排序（Cocktail Sort），也被称为双向冒泡排序，是一种改进的冒泡排序算法。它在冒泡排序的基础上进行了优化，通过双向遍历来减少排序时间。今天我们将学习如何在C
阅读更多...
快速排序（java代码实现）

快速排序（java代码实现）

简介： 1.采用“分治”的思想，对于一组数据，选择一个基准元素，这里选择中间元素mid 2.通过第一轮扫描，比mid小的元素都在mid左边，比mid大的元素都在mid右边 3.然后使用递归排序这两部分，直到序列中所有数据均有序为止。 public class csdnTest {public static void main(String[] args){int[] arr = {3,
阅读更多...
O(n)时间内对[0..n^-1]之间的n个数排序

O(n)时间内对[0..n^-1]之间的n个数排序

题目 如何在O(n)时间内，对0到n^2-1之间的n个整数进行排序 思路 把整数转换为n进制再排序，每个数有两位，每位的取值范围是[0..n-1]，再进行基数排序 代码 #include <iostream>#include <cmath>using namespace std;int n, radix, length_A, digit = 2;void Print(int *A,
阅读更多...
常用排序算法分析

常用排序算法分析

1. 插入排序 1.1 性能分析 时间复杂度O(n^2), 空间复杂度O(1) 排序时间与输入有关：输入的元素个数；元素已排序的程度。 最佳情况，输入数组是已经排好序的数组，运行时间是n的线性函数； 最坏情况，输入数组是逆序，运行时间是n的二次函数。 1.2 核心代码 public void sort(){int temp;for(int i = 1; i<arraytoSort.
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2