排序算法复习
排序算法好多都忘了，想复习一下， 顺便留个资料给自己, 最近正好有学C++, 所以用Python和C++都实现一遍
什么是稳定性:
- 稳定: 有数a与数b, a在b之前, 且a == b, 排序后a依然在b之前
- 不稳定: 有数a与数b, a在b之前, 且a == b, 排序后b可能在a之前
1冒泡排序(稳定)（O(n^2)）
思想: 从数组开头不断比对两个相邻的数， 如果后面的数比前面的大， 就把位置互换，从开头比到最后，这样最大的数就已经在数组的最后面了， 也就是说最大的数已经找到它的位置了， 然后把这个最大的数排除，再从前往后比较， 就能找到第二大的数， 循环比较， 一直到发现最小的数为止，最小的数也就是排序后数组里的第一个数
参考动图
Python求解
def solution(arr):
length = len(arr)
for i1 in range(length-1, 0, -1):
for i2 in range(i1):
if arr[i2] <= arr[i2+1]:
continue
arr[i2], arr[i2+1] = arr[i2+1], arr[i2]
return arr
C++求解
# include <iostream>
# include <algorithm>
using namespace std;
void solution(int arr[], int size){
for (int i1=size-1; i1>0; i1--){
for (int i2=0; i2<i1; i2++){
if (arr[i2] > arr[i2+1]){
swap(arr[i2], arr[i2+1]);
}
}
}
}
int main(){
int arr[10] = {9, 8, 7, 6, 5, 4, 3, 2, 1, 0};
solution(arr, 10);
for (int i=0; i<10; i++){
cout << arr[i] << " ";
}
cout << endl;
return 0;
}
2.选择排序(不稳定)（O(n^2)）
从前往后或者从后往前遍历， 先找到最小的或者最大的元素，让它和数组第一个元素交换位置， 然后找第二小的， 跟另一个元素交换位置 直到找到第二大或第二小的元素为止， 为什么说它不稳定， 因为它转移大小是交换位置，比如说5 8 5 2 9， 第一次遍历 2与5互换位置， 这两两个 5 的顺序就被破坏了， 所以是不稳定排序
参考动图
Python求解
def select_sort(arr):
for i1 in range(len(arr)):
tmp_i = i1
for i2 in range(i1, len(arr)):
if arr[tmp_i] > arr[i2]:
tmp_i = i2
arr[tmp_i], arr[i1] = arr[i1], arr[tmp_i]
return arr
C++求解
# include <iostream>
# include <algorithm>
using namespace std;
void solution(int arr[], int size){
int tmp_i;
for (int i1=0; i1<size; i1++){
tmp_i = i1;
for (int i2=i1; i2<size; i2++){
if (arr[i2] < arr[tmp_i]){
tmp_i = i2;
}
}
swap(arr[tmp_i], arr[i1]);
}
}
int main(){
int arr[10] = {9, 8, 7, 6, 5, 4, 3, 2, 1, 0};
solution(arr, 10);
for (int i=0; i<10; i++){
cout << arr[i] << " ";
}
cout << endl;
return 0;
}
3.简单插入排序(O(n^2))(稳定)
思想是渐进的维护一个有序的序列， 比如说有10个元素的数组， 先维护第一到第二个元素，让这两个元素有序， 然后维护从第一到第三个元素， 让这三个元素有序， 然后维护前四个， 给第四个元素找到适合它的位置， 让四个元素有序， 一直到最后一个元素加到这个序列中，让整个元素有序
参考动图
Python求解
def insert_sort(arr):
for i1 in range(1, len(arr)):
tmp = arr[i1]
for i2 in range(i1)[::-1]:
if arr[i2] > tmp:
arr[i2+1] = arr[i2]
if i2 == 0:
arr[i2] = tmp
else:
arr[i2+1] = tmp
break
return arr
# 看着if i2 == 0 贼难受， 不想加镶套循环， 以后有时间把这个想办法去掉了
C++求解
# include <iostream>
# include <algorithm>
using namespace std;
void solution(int arr[], int size){
int tmp;
for (int i1=1; i1<size; i1++){
tmp = arr[i1];
for (int i2=i1-1; i2>=0; i2--){
if (tmp > arr[i2]){
arr[i2+1] = tmp;
}else{
arr[i2+1] = arr[i2];
if (i2==0){
arr[i2] = tmp;
}
}
}
}
}
int main(){
int arr[10] = {9, 8, 7, 6, 5, 4, 3, 2, 1, 0};
solution(arr, 10);
for (int i=0; i<10; i++){
cout << arr[i] << " ";
}
cout << endl;
return 0;
}
4.希尔排序(平均复杂度小于O(n^1.3) 最大复杂度 O(n^2), 最好为O(n))(不稳定)
希尔排序是第一批突破O(n^2)的排序算法， 其是对简单插入排序的优化， 因为简单插入排序对基本有序的数组进行排序的时候效率是比较高的，所以希尔排序希望在简单排序之前通过尽可能少的交换与对比次数让数组变的基本有序， 具体的做法是设定一个跨度， 比如有10个元素需要排序， 第一次设定一个跨度5，第1个元素和第6个元素作对比， 小的放前面， 第2个元素和第7个作对比.... 这样10个元素就对比了5次， 最少让5个比较小的元素排在了前5个元素之前， 第二次再设定一个跨度2, 选择出两组数组， 对着两组分别进行简短插入排序， 最后跨度再设置为1，最后做一次简单排序， 注意， 此时的数组是基本有序了， 需要对比与插入的次数会非常少， 这样就提高了效率 另外: 关于增量跨度的选择非常重要， 对于同一个数组来说， 选择不同的增量程序的运行速度会天差地别， 最原始的是使用希尔增量， 也就是数组总长度/2, 但是这样会有一些极端情况产生， 参考文档: https://www.cnblogs.com/minxiang-luo/p/12392634.html
参考动图(原始希尔增量), 其中每一遍会把相同颜色的元素当做一个数组进行插入排序
Python求解
def shell_sort(arr):
span_num = int(len(arr) / 2)
while span_num > 0:
for i1 in range(span_num, len(arr)):
i2 = i1 - span_num
tmp = arr[i1]
while arr[i2] > tmp and i2 >= 0:
arr[i2+span_num] = arr[i2]
i2 -= span_num
arr[i2+span_num] = tmp
span_num = int(span_num / 2)
return arr
C++求解
# include <iostream>
# include <math.h>
using namespace std;
void solution(int arr[], int size){
int spanNum = floor(size/2);
int tmp;
while (spanNum > 0){
for (int i=spanNum; i<size; i++){
tmp = arr[i];
int i2 = i - spanNum;
while (i2 >= 0 and tmp < arr[i2]){
arr[i2+spanNum] = arr[i2];
i2 -= spanNum;
}
arr[i2+spanNum] = tmp;
}
spanNum = floor(spanNum/2);
}
}
int main(){
int arr[10] = {9, 8, 7, 6, 5, 4, 3, 2, 1, 0};
solution(arr, 10);
for (int i=0; i<10; i++){
cout << arr[i] << ' ';
}
cout << endl;
return 1;
}
5.归并(复杂度O(nlog2n))(稳定)
经典分治的排序应用，一样突破了n^2的排序算法， 以空间换时间， 空间复杂度略微比较高算是递归通病，核心思想是把一个数组拆成两个数组， 每个数组再拆成两个数组， 直到数组变的有序， 其实就是拆到只有一个元素的数组， 然后向上合并， 去把两个有序数组组合， 这时候是重点， 它快就快在这， 合并两个有序数组的时候原则上只需要一次遍历就解决了，比如合并 [1 3 5] [2 4 6], 把他们放到一个新数组[]里， 比对两个数组的第一个元素， 谁小就把谁放到新的数组里， 比如第一次比对1 和 2 把 1 放到数组里，新数组为[1] 第二次比对 3 和 2 把 2放到数组里就变成[1,2]持续这个过程，如果有某个数组为空了， 就把另一个数组直接拼接到新数组后面就成了[1,2,3,4,5,6]
参考动图
Python求解
def merge_sort(arr):
length = len(arr)
if length <= 1:
return arr
span_num = int(length/2)
left = merge_sort(arr[:span_num])
right = merge_sort(arr[span_num:])
i = 0
left_i = 0
right_i = 0
while i < length:
if right_i == len(right):
arr[i] = left[left_i]
left_i += 1
elif left_i == len(left):
arr[i] = right[right_i]
right_i += 1
elif right[right_i] < left[left_i]:
arr[i] = right[right_i]
right_i += 1
else:
arr[i] = left[left_i]
left_i += 1
i += 1
return arr
C++求解
# include <iostream>
using namespace std;
void solution(int arr[], int size){
if (size <= 1){
return;
}
int spanNum = floor(size/2);
int leftSize = spanNum;
int rightSize = size - spanNum;
int *left = new int[leftSize];
int *right = new int[rightSize];
for (int i=0; i<leftSize; i++){
left[i] = arr[i];
}
for (int i=0; i<rightSize; i++){
right[i] = arr[i+spanNum];
}
solution(left, leftSize);
solution(right, rightSize);
int i = 0;
int left_i = 0;
int right_i = 0;
while (i < size){
if (left_i == leftSize){
arr[i] = right[right_i];
right_i++;
}
else if (right_i == rightSize){
arr[i] = left[left_i];
left_i++;
}
else if (right[right_i] < left[left_i]){
arr[i] = right[right_i];
right_i++;
}
else{
arr[i] = left[left_i];
left++;
}
i++;
}
delete[] left;
delete[] right;
}
int main(){
int arr[10] = {9, 8, 7, 6, 5, 4, 3, 2, 1, 0};
solution(arr, 10);
for (int i=0; i<10; i++){
cout << arr[i] << ' ';
}
cout << endl;
return 1;
}
6.快速排序(复杂度波动较大)(不稳定)
基本思想是随便从数组里找到一个数， 通常来讲是第一个数， 然后确定它的位置， 确定的方法就是比这个数小的都在这个数的左边，比他大的都在它的右边，然后对他的最后子序列分别做这样的操作，递归地做出来， 直到子序列小于等于1 举个例子: [2,3,1,5,4] 第一次把2在数组里的位置确定， 比如先把2拿出来数组变成[,3,1,5,4], 想象有个两个指针分别指在 原来2 与 4的位置， left_index=0 right_index=4, 先判断右侧的指针是否比2小，发现不小， 指针在对比 5 发现也不小， 继续移动右侧指针， 当找到right_indx=2 找到值为1的元素的时候， 把1拿到2的位置上， 数组变成了[1,3,,5,4], 现在右侧指针先不动， 移动左侧指针到left_index=1, 发现3比2大， 需要放到右边，也就是现在right_index的地方， 数组变成了[1,,3,5,4], 然后移动右侧指针， 发现 left_index=1 right_index=1, 下标一致， 这个下标就是2应该在的位置， 数组就变成了[1,2,3,5,4], 然后对2的左右两侧子序列分别做同样的操作也就是序列[1] [3,5,4], 不断地递归让子序列都有序，这样就完成了，参考链接: https://zhuanlan.zhihu.com/p/63202860
Python求解
def quick_sort(arr, left=None, right=None):
left = 0 if left is None else left
right = len(arr) if right is None else right
left_i = left
right_i = right
if right_i - left_i <= 1:
return arr
flag = True
tmp = arr[left_i]
while left_i != right_i:
if flag:
right_i -= 1
if arr[right_i] < tmp:
arr[left_i] = arr[right_i]
flag = False
else:
left_i += 1
if arr[left_i] > tmp:
arr[right_i] = arr[left_i]
flag = True
arr[left_i] = tmp
quick_sort(arr, left, left_i)
quick_sort(arr, left_i+1, right)
return arr
C++求解
# include <iostream>
using namespace std;
void solution(int arr[], int size, int left=0, int right=-1){
if (right == -1){
right = size;
}
if (right - left <= 1){
return;
}
int left_i = left;
int right_i = right;
int tmp = arr[left_i];
bool flag = true;
while (left_i !=right_i){
if (flag){
right_i--;
if (arr[right_i] < tmp){
arr[left_i] = arr[right_i];
flag = false;
}
}else{
left_i++;
if (arr[left_i] > tmp){
arr[right_i] = arr[left_i];
flag = true;
}
}
}
arr[left_i] = tmp;
solution(arr, size, left, left_i);
solution(arr, size, left_i+1, right);
}
int main(){
int arr[10] = {9, 8, 7, 6, 5, 4, 3, 2, 1, 0};
solution(arr, 10);
for (int i=0; i<10; i++){
cout << arr[i] << ' ';
}
cout << endl;
return 1;
}
7.堆排序(nlog2n)(不稳定)
再看其他的文档之前请参考我的理解， 这样会好理解很多: 先不管堆排序使用了什么完全二叉树， 实际可以把堆排序和冒泡排序的一些思想作对比， 他们很像!!!, 为啥这么说？ 冒泡排序每次循环都会找到一个最大的数， 然后放到数组最后面， 然后再把这个最大的数排除， 找到第二大的放到最大的前面， 然后把这俩排除， 堆排序也差不多， 只不过堆排序不是每次通过冒泡排序那种逐个比对，而是巧妙地用了完全二叉树的大顶堆或者小顶堆的一些特性，比如它的根节点肯定是最大或者最小的， 这样不就像冒泡一样把最大的数找到了么？ 然后紧接着把最大的数放到最后，排除这个最大数， 再用剩下的数组构建一个完全二叉树， 根节点最大，循环这么做这个数组不就变的有序了么？ 很多文档会先给你扯一堆二叉树，完全二叉树， 大顶堆， 小顶堆， 看着抓不住重点， 再看其他文档的时候你就先在心里有个基本思路: 堆排序只是用数组表达二叉树， 然后对这个二叉树进行排序，之后就得到最大的数了， 然后循环去找到剩余的最大数， 最后就可以翻阅二叉树相关资料了， 比如大顶堆小顶堆， 每个节点的子节点索引， 怎么去让二叉树根节点大于所有子节点， 可参考文档: https://zhuanlan.zhihu.com/p/142095184 再多说一句:为什么二叉树会快一些: 因为树的高度近似log2n，从一个最下面的叶节点对比到跟节点次数会变得少， 不像冒泡每次要挨个对比， 这个是跳着对比的..... 对比的少了， 自然就快了...... 这个参考资料非常不错: https://zhuanlan.zhihu.com/p/142095184
参考动图
Python求解
# 代码比较简单， 应该可以正常工作， 不知道别人怎么写， 我是按照从最后的子叶节点开始遍历的
def heap_sort(arr):
for num in range(len(arr)):
num = (len(arr) - num)
i = int(num / 2) - 1
while i >= 0:
i1 = 2 * i + 1
i2 = 2 * i + 2
if i1 < num and arr[i] < arr[i1]:
arr[i1], arr[i] = arr[i], arr[i1]
if i2 < num and arr[i] < arr[i2]:
arr[i2], arr[i] = arr[i], arr[i2]
i -= 1
# 学习的时候可以加个打印看看每次二叉树找到最大后的数组，加深理解
# print(arr)
arr[num-1], arr[0] = arr[0], arr[num-1]
return arr
C++求解
# include <iostream>
# include <math.h>
using namespace std;
void solution(int arr[], int size){
int i;
int i1;
int i2;
for (int num=size; num>0; num--){
int i = floor(num / 2) - 1;
while (i >= 0){
i1 = i * 2 + 1;
i2 = i * 2 + 2;
if (i1 < num and arr[i1] > arr[i]){
swap(arr[i1], arr[i]);
}
if (i2 < num and arr[i2] > arr[i]){
swap(arr[i2], arr[i]);
}
i--;
}
swap(arr[0], arr[num-1]);
}
}
int main(){
int arr[10] = {9, 8, 7, 6, 5, 4, 3, 2, 1, 0};
solution(arr, 10);
for (int i=0; i<10; i++){
cout << arr[i] << ' ';
}
cout << endl;
return 1;
}
8.计数排序(O(n+k))(稳定)
简单的说是用空间换时间的算法， 其核心含义是把待排序的每个数值当做索引， 映射到一个新的数组，比如数组 [3, 1, 3], 这个数组最大为3， 那就建立一个长度为3+1=4的数组， 比如[0, 0, 0, 0], 遍历[3, 1, 3], 新数组变为[0, 1, 0, 2], 原来的数组当做了新数组的索引， 其值为数组出现的次数 备注1: 这个排序方法在我看来及其不稳定， 如果要排序的数组为[-10000, 100000000000], 这样的话要生成一个极大的空间来进行一个简单的排序， 一旦产生极大数或者极小数，空间复杂度与时间复杂度都会极大地提升 备注2: 关于代码演示就先不考虑会有负数的情况， 如果有负数的话还需要把最小值找出来取绝对值作为增量， 不利于理解
参考动图
Python求解
def count_sort(arr):
if not arr:
return arr
max_i = max(arr) + 1
arr_info = [0 for _ in range(max_i)]
for i in arr:
arr_info[i] += 1
i1 = 0
for i2 in range(max_i):
for _ in range(arr_info[i2]):
arr[i1] = i2
i1 += 1
return arr
C++求解
# include <iostream>
# include <math.h>
using namespace std;
void solution(int arr[], int size){
int maxValue = *max_element(arr,arr+size) + 1;
int *arrInfo = new int[maxValue];
for (int i=0; i<size; i++){
arrInfo[arr[i]]++;
}
int index = 0;
for (int i=0; i<maxValue; i++){
for (int tmp=0; tmp<arrInfo[i]; tmp++){
arr[index] = i;
index++;
}
}
delete [] arrInfo;
}
int main(){
int arr[10] = {13,10,11,9,5,8,3,2,1};
solution(arr, 9);
for (int i=0; i<9; i++){
cout << arr[i] << ' ';
}
cout << endl;
return 0;
}
9.桶排序(稳定)
桶排序是计数排序的升级版， 比如排序的数组为[0, 100000000000], 用计数排序的话，这样的话要生成一个极大的空间来进行一个简单的排序, 要生成100000000000 + 1这样长度的数组， 资源浪费太大了， 所以个人理解桶排序实际就是对这种情况的优化，可以自定义这个数组的长度，比如这个例子就可以生成长度是两个的数组， 每个元素都是一个"桶"， 这个桶是容器， 容纳相同范围的数， 就可以分成这样的一个结构: [[0], [100000000000]] 然后对每个元素再分别排序， 既可以用桶排序又可以用其他排序，至于怎么定义桶的个数与怎么把每个相同范围的元素映射到相同的桶里的计算方式很多我个人比较喜欢的计算方式是这样(《算法导论》里讲桶排序也是多少个元素用多少个桶): n个元素， n个桶，桶的序号从0到n-1 最大值是max， 最小值是min, 判断数v应该在哪个桶里 桶的序号为: ceil((v - min)/(max-min)/n) - 1
Python求解
def bucket_sort(arr):
if len(arr) < 2:
return arr
num_min = min(arr)
num_max = max(arr)
if num_min == num_max:
return arr
tmp_num = (num_max - num_min) / float(len(arr))
arr_info = [[] for _ in range(len(arr))]
for i in arr:
bucket_i = int(math.ceil((i - num_min)/tmp_num) - 1)
if bucket_i < 0:
bucket_i = 0
arr_info[bucket_i].append(i)
i = 0
for tmp_arr in arr_info:
bucket_sort(tmp_arr)
for tmp in tmp_arr:
arr[i] = tmp
i += 1
return arr
C++求解
# include <iostream>
# include <math.h>
# include <vector>
# include <string>
using namespace std;
// 因为c++学习的不久, 理解的不够深入, 空间复杂度与时间复杂度处理的不好, 但算法意思表达出来了
void solution(int arr[], int size){
if (size < 2){
return;
}
int maxValue = *max_element(arr,arr+size);
int minValue = *min_element(arr,arr+size);
if (maxValue == minValue){
return;
}
float tmpValue = (float)(maxValue - minValue) / (float)size;
int tmpNum;
int index = 0;
// vector < vector<int> > arrInfo(size);
vector < vector<int> > arrVector;
for (int i=0; i<size; i++){
vector < int > tmpVector;
arrVector.push_back(tmpVector);
}
for (int i=0; i<size; i++){
tmpNum = ceil((arr[i] - minValue) / tmpValue) - 1;
if (tmpNum < 0){
tmpNum = 0;
}
arrVector[tmpNum].push_back(arr[i]);
}
for (int i=0; i<size; i++){
int arrTmp[arrVector[i].size()];
for (int i2=0; i2<arrVector[i].size(); i2++){
arrTmp[i2]=arrVector[i][i2];
}
solution(arrTmp, arrVector[i].size());
for (int i2=0; i2<arrVector[i].size(); i2++){
arr[index] = arrTmp[i2];
index++;
}
}
}
int main(){
int arr[10] = {13,10,11,9,5,8,3,2,1};
solution(arr, 9);
for (int i=0; i<9; i++){
cout << arr[i] << ' ';
}
cout << endl;
return 0;
}
10.基数排序(稳定)
基数排序也属于桶排序的一种(计数排序实际也是桶排序的一种), 原理是将十进制比如说 111 分成三部分， 个位 十位 百位, 举例[10 21, 9, 18， 31], 先按个位排序， 因为是十进制， 排序先准备十个桶，每个桶的内容为: [[10], [21, 31], [], [], [], [], [], [], [18], [9]], 然后按顺序放到数组里， 此时数组变为[10, 21, 31, 18, 9], 然后按十位进行排序， 如果没有十位则认为十位为0， 桶内容为 [[9], [10， 18], [21], [31], [], [], [], [], [18], [9]]， 因为最高位为两位数， 所以再按顺序放到数组里就排完了，如果最高位为3位或者更多，则需要排更多次，排序后为: [9, 10, 18, 21, 31] 备注: 改算法步骤固定， 排多少次取决于最高位， 当最高位比较小的时候这个算法比较实用， 占用空间也是固定的， 然后排序的过程中没发生位置交换， 所以属于稳定排序
Python求解
def radix_sort(arr):
"""
从低位往高位排(也可从高往低排, 但是需要知道最高位或者设置一个最高位)
"""
arrInfo = [[] for _ in range(10)]
max_bit = 0
current_bit = 0
while current_bit <= max_bit:
for i in arr:
info = str(i)
if len(info) - 1 > max_bit:
max_bit = len(info) - 1
if len(info) <= current_bit:
index = 0
else:
index = int(info[len(info) - current_bit - 1])
arrInfo[index].append(i)
i = 0
for tmp in arrInfo:
for value in tmp:
arr[i] = value
i += 1
tmp.clear()
del tmp[:]
current_bit += 1
return arr
C++求解
# include <iostream>
# include <math.h>
# include <vector>
# include <string>
using namespace std;
void solution(int arr[], int size){
if (size < 2){
return;
}
int maxBit = 0;
int currentBit = 0;
string tmpString;
int tmpNum;
vector < vector<int> > arrVector;
for (int i=0; i<10; i++){
vector <int> tmpVector;
arrVector.push_back(tmpVector);
}
while (currentBit <= maxBit){
for (int i=0; i<size; i++){
tmpString = to_string(arr[i]);
if (tmpString.size() - 1 >= maxBit){
maxBit = tmpString.size() - 1;
}
if (tmpString.size() <= currentBit){
tmpNum = 0;
} else {
tmpString = tmpString[tmpString.size() - currentBit - 1];
tmpNum = atoi(tmpString.c_str());
}
arrVector[tmpNum].push_back(arr[i]);
}
tmpNum = 0;
for (int i=0; i<10; i++){
for (int i2=0; i2<arrVector[i].size(); i2++){
arr[tmpNum] = arrVector[i][i2];
tmpNum++;
}
arrVector[i].clear();
}
currentBit++;
}
}
int main(){
int arr[10] = {13,10,11,9,5,8,3,2,1};
solution(arr, 9);
for (int i=0; i<9; i++){
cout << arr[i] << ' ';
}
cout << endl;
return 0;
}
完...
查看12道真题和解析
