devbox
盐析白兔
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

10种排序算法总结及c++代码_算法与设计zhijiecharupaixudaima

作者：盐析白兔 | 2024-03-21 03:29:24

赞

踩

算法与设计zhijiecharupaixudaima

排序算法总结

1.冒泡排序

冒泡排序是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。

算法描述

  1. 比较相邻的元素。如果第一个比第二个大，就交换它们两个；
  2. 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数；
  3. 针对所有的元素重复以上的步骤，除了最后一个；
  4. 重复步骤1~3，直到排序完成。

img

void bubble(vector<int> &nums){
    int len=nums.size();
    bool swap;
    for(int i=0;i<len;i++){
        swap =false;//优化：如果一趟排序中没有交换位置，则说明元素已经有序
        for(int j=1;j<len-i;j++){
            if(nums[j-1]>nums[j]){
                int temp = nums[j];
                nums[j] = nums[j-1];
                nums[j-1]=temp;
                swap=true;
            }
        }
        if(!swap){
            break;
        }
    }
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18

稳定性

在相邻元素相等时，它们并不会交换位置，所以，冒泡排序是稳定排序。

适用场景

冒泡排序思路简单，代码也简单，特别适合小数据的排序。但是，由于算法复杂度较高，在数据量大的时候不适合使用。

代码优化(上面代码已经优化了)

在数据完全有序的时候展现出最优时间复杂度，为O(n)。其他情况下，几乎总是 O ( n 2 ) O( n^2 ) O(n2)。因此，算法在数据基本有序的情况下，性能最好。
要使算法在最佳情况下有O(n)复杂度，需要做一些改进，增加一个swap的标志，当前一轮没有进行交换时，说明数组已经有序，没有必要再进行下一轮的循环了，直接退出。

2.选择排序

选择排序是一种简单直观的排序算法，它也是一种交换排序算法，和冒泡排序有一定的相似度，可以认为选择排序是冒泡排序的一种改进。

算法描述

  1. 在未排序序列中找到最小（大）元素，存放到排序序列的起始位置
  2. 从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。
  3. 重复第二步，直到所有元素均排序完毕。

img

void selectSort(vector<int> &arr){
    for(int i=0;i<arr.size();i++){
        int minIndex = i;
        for(int j=i+1;j<arr.size();j++){
            if(arr[minIndex]>arr[j]){
                minIndex = j;
            }
        }
        if(minIndex!=i){
            int temp = arr[i];
            arr[i] = arr[minIndex];
            arr[minIndex]=temp;
        }
    }
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15

稳定性

用数组实现的选择排序是不稳定的，用链表实现的选择排序是稳定的。
不过，一般提到排序算法时，大家往往会默认是数组实现，所以选择排序是不稳定的。

选择排序为啥不是稳定性排序呢，举个例子：数组 6、7、6、2、8，在对其进行第一遍循环的时候，会将第一个位置的6与后面的2进行交换。此时，就已经将两个6的相对前后位置改变了。因此选择排序不是稳定性排序算法。

适用场景

选择排序实现也比较简单，并且由于在各种情况下复杂度波动小，因此一般是优于冒泡排序的。在所有的完全交换排序中，选择排序也是比较不错的一种算法。但是，由于固有的 O ( n 2 ) O(n^2) O(n2)复杂度，选择排序在海量数据面前显得力不从心。因此，它适用于简单数据排序。

3.插入排序

插入排序是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

算法描述

  1. 把待排序的数组分成已排序和未排序两部分，初始的时候把第一个元素认为是已排好序的。
  2. 从第二个元素开始，在已排好序的子数组中寻找到该元素合适的位置并插入该位置。
  3. 重复上述过程直到最后一个元素被插入有序子数组中。

img

void InsertionSort(int *a,int len)
{
    for(int i=1;i<len;i++){
        int key = a[i];
        int j=i-1;
        for(;j>=0&&a[j]>key;j--)
        {
            a[j+1]=a[j];
        }
        nums[j+1]=key;
    }
}
/*
void InsertSort(vector<int> &vec) {
	for (int i = 1; i < vec.size(); i++) {
		int j = i - 1;
		int key = vec[i];
		for (; j >= 0 && vec[j] > key; j--) {
			vec[j + 1] = vec[j];
		}
		vec[j + 1] = key;
	}
}*/

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23

稳定性

由于只需要找到不大于当前数的位置而并不需要交换，因此，直接插入排序是稳定的排序方法。

适用场景

插入排序由于 O ( n 2 ) O( n^2 ) O(n2)的复杂度，在数组较大的时候不适用。但是，在数据比较少的时候，是一个不错的选择，一般做为快速排序的扩充。

4.归并排序

归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。

算法描述

两种方法

  • 递归法（Top-down）
  1. 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
  2. 设定两个指针，最初位置分别为两个已经排序序列的起始位置
  3. 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
  4. 重复步骤3直到某一指针到达序列尾
  5. 将另一序列剩下的所有元素直接复制到合并序列尾

  • 迭代法（Bottom-up）

    原理如下（假设序列共有n个元素）：

  1. 将序列每相邻两个数字进行归并操作，形成ceil(n/2)个序列，排序后每个序列包含两/一个元素
  2. 若此时序列数不是1个则将上述序列再次归并，形成ceil(n/4)个序列，每个序列包含四/三个元素
  3. 重复步骤2，直到所有元素排序完毕，即序列数为1

img

//C++ 版本 递归实现
#include<vector>
#include<iostream>
using namespace std;
void Merge(vector<int> &vec, int start, int mid, int end) {
	int leftIndex = start;
	int rightIndex = mid + 1;
	vector<int> temp(end-start+1);
	int tempIndex = 0;
	while (leftIndex <= mid && rightIndex <= end) {
		if (vec[leftIndex] <= vec[rightIndex]) {
			temp[tempIndex++] = vec[leftIndex++];
		}
		else {
			temp[tempIndex++] = vec[rightIndex++];
		}
	}
	while (leftIndex <= mid) {
		temp[tempIndex++] = vec[leftIndex++];
	}
	while (rightIndex <= end) {
		temp[tempIndex++] = vec[rightIndex++];
	}
	for (int i = start; i <= end; i++) {
		vec[i] = temp[i - start];
	}
}

void MergeSort(vector<int> &vec, int start, int end) {
	if (start >= end) {
		return;
	}
	int mid = (start + end) / 2;
	MergeSort(vec, start, mid);
	MergeSort(vec, mid + 1, end);
	Merge(vec, start, mid, end);
}

int main() {
	vector<int> a = { 5,6,1,8,3,4,9,7,2,3 };
	cout << "归并排序前：";
	for (int i = 0; i < 10; i++)
		cout << a[i] << ' ';
	cout << endl;

	MergeSort(a, 0, 9);

	cout << "归并排序后：";
	for (int i = 0; i < 10; i++)
		cout << a[i] << ' ';
	cout << endl;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52

稳定性

因为我们在遇到相等的数据的时候必然是按顺序“抄写”到辅助数组上的，所以，归并排序同样是稳定算法。

适用场景

归并排序在数据量比较大的时候也有较为出色的表现（效率上），但是，其空间复杂度O(n)使得在数据量特别大的时候（例如，1千万数据）几乎不可接受。而且，考虑到有的机器内存本身就比较小，因此，采用归并排序一定要注意。

5.快速排序

通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

中心思想就是：找一个基准值，把数据分为两部分，然后去排序，类似于二分查找。

算法描述

  1. 从数列中挑出一个元素，称为"基准"（pivot），
  2. 重新排序数列，所有比基准值小的元素摆放在基准前面，所有比基准值大的元素摆在基准后面（相同的数可以到任何一边）。在这个分区结束之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。
  3. 递归地（recursively）把小于基准值元素的子数列和大于基准值元素的子数列排序。

img

递归版

void quicksort(vector<int>&vec,int left,int right){
    int i=left;
    int j=right;
    int temp = vec[left];
    while(i<j){
        while(i<j&&vec[j]>=temp)j--;   //注意是大于等于，没有等于可能会陷入死循环
        vec[i]=vec[j];
        while(i<j&&vec[i]<=temp)i++;
        vec[j]=vec[i];
    }
    vec[i]=temp;
    if(i-left-1>0){
        quicksort(vec,left,i-1);
    }
    if(right-i-1>0){
        quicksort(vec,i+1,right);
    }
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18

非递归版

void quickstack(vector<int> &vec,int left,int right){
	stack<int> st;
    st.push(left);
    st.push(right);
    while(!st.empty()){
        int j = st.top();
        right = j;
        st.pop();
        int i=st.top();
        left = i;
        st.pop();
        int temp=vec[left];
        while(i<j){
            while(i<j&&vec[j]>=temp)j--;
            vec[i]=vec[j];
            while(i<j&&vec[i]<=temp)i++;
            vec[j]=vec[i];
        }
        vec[i]=temp;
        if(i-left-1>0){
            st.push(left);
            st.push(i-1); 
        }
        if(right-i-1>0){
            st.push(i+1);
            st.push(right);
        }
    }
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29

稳定性

快速排序并不是稳定的。这是因为我们无法保证相等的数据按顺序被扫描到和按顺序存放。

适用场景

快速排序在大多数情况下都是适用的，尤其在数据量大的时候性能优越性更加明显。但是在必要的时候，需要考虑下优化以提高其在最坏情况下的性能。

6.堆排序

堆排序是借助堆来实现的选择排序，思想同简单的选择排序，以下以大顶堆为例。注意：如果想降序排序就使用大顶堆，反之使用小顶堆。原因是堆顶元素需要交换到序列尾部。

总体复杂度为O(n*log n)

稳定速度快，topk排序会用到(在很多数据里面找前几个)

首先，实现堆排序需要解决两个问题：

 　　1. 如何由一个无序序列键成一个堆？

      2. 如何在输出堆顶元素之后，调整剩余元素成为一个新的堆？

  • 1
  • 2
  • 3

第一个问题，可以直接使用线性数组来表示一个堆，由初始的无序序列建成一个堆就需要自底向上从第一个非叶元素开始挨个调整成一个堆。

第二个问题，怎么调整成堆？首先是将堆顶元素和最后一个元素交换。然后比较当前堆顶元素的左右孩子节点，因为除了当前的堆顶元素，左右孩子堆均满足条件，这时需要选择当前堆顶元素与左右孩子节点的较大者（大顶堆）交换，直至叶子节点。我们称这个自堆顶自叶子的调整成为筛选。

从一个无序序列建堆的过程就是一个反复筛选的过程。若将此序列看成是一个完全二叉树，则最后一个非终端节点是n/2取底个元素，由此筛选即可。举个栗子：

49,38,65,97,76,13,27,49序列的堆排序建初始堆和调整的过程如下：

image-20201215162728440

算法过程

https://www.cnblogs.com/wanglei5205/p/8733524.html

  • 步骤一：建立大根堆–将n个元素组成的无序序列构建一个大根堆，

  • 步骤二：交换堆元素–交换堆尾元素和堆首元素，使堆尾元素为最大元素；

  • 步骤三：重建大根堆–将前n-1个元素组成的无序序列调整为大根堆

    重复执行步骤二和步骤三，直到整个序列有序。

#include<iostream>
#include<vector>
using namespace std;
 
// 递归方式构建大根堆(len是arr的长度，index是第一个非叶子节点的下标)
void adjust(vector<int> &arr, int len, int index)
{
    int left = 2*index + 1; // index的左子节点
    int right = 2*index + 2;// index的右子节点
 
    int maxIdx = index;
    if(left<len && arr[left] > arr[maxIdx])     maxIdx = left;
    if(right<len && arr[right] > arr[maxIdx])     maxIdx = right;
 
    if(maxIdx != index)
    {
        swap(arr[maxIdx], arr[index]);
        adjust(arr, len, maxIdx);
    }
}
 
// 堆排序
void heapSort(vector<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()
{
    vector<int> arr = {8, 1, 14, 3, 21, 5, 7, 10};
    heapSort(arr, arr.size());
    for(int i=0;i<arr.size();i++)
    {
        cout<<arr[i]<<endl;
    }
    return 0;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48

稳定性

堆排序存在大量的筛选和移动过程，属于不稳定的排序算法。

适用场景

堆排序在建立堆和调整堆的过程中会产生比较大的开销，在元素少的时候并不适用。但是，在元素比较多的情况下，还是不错的一个选择。尤其是在解决诸如“前n大的数”一类问题时，几乎是首选算法。

7 希尔排序

（插入排序的改良版）

在希尔排序出现之前，计算机界普遍存在“排序算法不可能突破O(n2)”的观点。希尔排序是第一个突破O(n2)的排序算法，它是简单插入排序的改进版。希尔排序的提出，主要基于以下两点：

  1. 插入排序算法在数组基本有序的情况下，可以近似达到O(n)复杂度，效率极高。
  2. 但插入排序每次只能将数据移动一位，在数组较大且基本无序的情况下性能会迅速恶化。

算法描述

先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，具体算法描述：

  • 选择一个增量序列t1，t2，…，tk，其中ti>tj，tk=1；
  • 按增量序列个数k，对序列进行 k 趟排序；
  • 每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m 的子序列，分别对各子表进行直接插入排序。仅增量因子为1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。

img

void ShellSort(vector<int> &arr) {
	int n = arr.size();
	
	for (int increment = n / 2; increment > 0; increment /= 2) {
		for (int i = increment; i < n; i++) {
			int temp=arr[i];
			int j = i;
			for (; j >= increment; j -= increment) {
				if (temp < arr[j - increment]) {
					arr[j] = arr[j - increment];
				}
				else {
					break;
				}
			}
			arr[j] = temp;
		}
	}
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
void ShellSort(vector<int> &arr) {
	int n = arr.size();
	
	for (int increment = n / 3; increment > 0; increment /= 3) {
		for (int i = increment; i < n; i++) {
			int temp=arr[i];
			int j = i;
			for (; j >= increment; j -= increment) {
				if (temp < arr[j - increment]) {
					arr[j] = arr[j - increment];
				}
				else {
					break;
				}
			}
			arr[j] = temp;
		}
	}
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19

希尔排序是为了冲破二次时间的屏障，但是最终证明，其时间最坏情况为 O ( N 2 ) O(N^2) O(N2)。

希尔排序的增量

希尔排序的增量数列可以任取，需要的唯一条件是最后一个一定为1（因为要保证按1有序）。但是，不同的数列选取会对算法的性能造成极大的影响。上面的代码演示了两种增量。
切记：增量序列中每两个元素最好不要出现1以外的公因子！（很显然，按4有序的数列再去按2排序意义并不大）。
下面是一些常见的增量序列。
- 第一种增量是最初Donald Shell提出的增量，即折半降低直到1。据研究，使用希尔增量，其时间复杂度还是O(n2)。

第二种增量Hibbard：{1, 3, …, 2k-1}。该增量序列的时间复杂度大约是O(n1.5)。

第三种增量Sedgewick增量：(1, 5, 19, 41, 109,…)，其生成序列或者是 9 ∗ 4 i − 9 ∗ 2 i + 1 或 者 是 4 i − 3 ∗ 2 i + 1 9*4i- 9*2i + 1或者是4i - 3*2i + 1 9∗4i−9∗2i+1或者是4i−3∗2i+1。

稳定性

我们都知道插入排序是稳定算法。但是，Shell排序是一个多次插入的过程。在一次插入中我们能确保不移动相同元素的顺序，但在多次的插入中，相同元素完全有可能在不同的插入轮次被移动，最后稳定性被破坏，因此，Shell排序不是一个稳定的算法。

适用场景

Shell排序虽然快，但是毕竟是插入排序，其数量级并没有后起之秀–快速排序O(n㏒n)快。在大量数据面前，Shell排序不是一个好的算法。但是，中小型规模的数据完全可以使用它。

8. 计数排序

计数排序不是基于比较的排序算法，其核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。 作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。

算法描述

  1. 找出待排序的数组中最大和最小的元素；
  2. 统计数组中每个值为i的元素出现的次数，存入数组count的第i-min项；
  3. 根据计数值对数组进行填充

img

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

void countSort(vector<int> &arr, int ma, int mi) {
	vector<int> count(ma - mi + 1,0);
	for (int i = 0; i < arr.size(); i++) {
		int num = arr[i];
		count[num - mi]++;
	}
	int index = 0;
	for (int i = 0; i <count.size(); i++) {
		while (count[i] != 0) {
			arr[index++] = i + mi;
			count[i]--;
		}
	}
}


int main()
{
	vector<int> arr = { 8, 1, 14, 3, 21, 5, 7, 10 };
	int mi = arr[0];
	int ma = arr[0];
	for (int i = 1; i < arr.size(); i++) {
		if (arr[i] > ma) {
			ma = arr[i];
		}
		if (arr[i] < mi) {
			mi = arr[i];
		}
	}
	
	countSort(arr,ma,mi);
	for (int i = 0; i < arr.size(); i++)
	{
		cout << arr[i] << " ";
	}
	cout << endl;
	return 0;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43

稳定性

最后不涉及相同元素顺序问题，从而保证了稳定性。

适用场景

排序目标要能够映射到整数域，其最大值最小值应当容易辨别。例如高中生考试的总分数，显然用0-750就OK啦；又比如一群人的年龄，用个0-150应该就可以了，再不济就用0-200喽。另外，计数排序需要占用大量空间，它比较适用于数据比较集中的情况。

9 桶排序

桶排序又叫箱排序，是计数排序的升级版，它的工作原理是将数组分到有限数量的桶子里，然后对每个桶子再分别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序），最后将各个桶中的数据有序的合并起来。

计数排序是桶排序的一种特殊情况，可以把计数排序当成每个桶里只有一个元素的情况。网络中很多博文写的桶排序实际上都是计数排序，并非标准的桶排序，要注意辨别。

算法描述

  1. 找出待排序数组中的最大值max、最小值min
  2. 我们使用 动态数组bucketArr作为桶，桶里放的元素也用bucketArr存储。桶的数量为(max-min)/arr.size()+1
  3. 遍历数组 arr，计算每个元素 arr[i] 放的桶
  4. 每个桶各自排序
  5. 遍历桶数组，把排序好的元素放进输出数组
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

void bucket_sort(vector<int> &arr) {
	int mi = arr[0];
	int ma = arr[0];
	for (int i = 1; i < arr.size(); i++) {
		if (arr[i] > ma) {
			ma = arr[i];
		}
		if (arr[i] < mi) {
			mi = arr[i];
		}
	}
	int bucketNum = (ma - mi) / arr.size() + 1;//桶数
	vector<vector<int>> bucketArr(bucketNum);
	//入桶
	for (int i = 0; i < arr.size(); i++) {
		int num = (arr[i] - mi) / arr.size();
		bucketArr[num].push_back(arr[i]);
	}
	//每个桶内部排序
	int index = 0;
	for (int i = 0; i < bucketArr.size(); i++) {
		sort(bucketArr[i].begin(), bucketArr[i].end());
		for (int j = 0; j < bucketArr[i].size(); j++) {
			arr[index++] = bucketArr[i][j];
		}
	}
	
}


int main() {
	vector<int> arr = { 1,1,2 };// { 8, 1, 14, 3, 21, 5, 7, 10 };
	bucket_sort(arr);
	for (int i = 0; i < arr.size(); i++)
	{
		cout << arr[i] << " ";
	}
	cout << endl;
	return 0;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45

稳定性

可以看出，在分桶和从桶依次输出的过程是稳定的。但是，由于我们在对每个桶进行排序时使用了其他算法，所以，桶排序的稳定性依赖于这一步。如果我们使用了快排，显然，算法是不稳定的。

适用场景

桶排序可用于最大最小值相差较大的数据情况，但桶排序要求数据的分布必须均匀，否则可能导致数据都集中到一个桶中。比如[104,150,123,132,20000], 这种数据会导致前4个数都集中到同一个桶中。导致桶排序失效。

10 基数排序

基数排序(Radix Sort)是桶排序的扩展，它的基本思想是：将整数按位数切割成不同的数字，然后按每个位数分别比较。
排序过程：将所有待比较数值（正整数）统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列。

算法描述

  1. 取得数组中的最大数，并取得位数；
  2. arr为原始数组，从最低位开始取每个位组成radix数组；
  3. 对radix进行计数排序（利用计数排序适用于小范围数的特点）；

img

//找到最大值
int computeMax(vector<int> &arr) {
	int ma = arr[0];
	for (int i = 1; i < arr.size(); i++) {
		if (arr[i] > ma) {
			ma = arr[i];
		}
	}
	return ma;
}

//最长的位数
int getDistance(vector<int> &arr) {
	int ma = computeMax(arr);
	int digits = 0;

	while (ma != 0) {
		digits++;
		ma = ma / 10;
	}
	return digits;
}


void radixSort(vector<int>& arr) {

	vector<vector<int>> buckets(10,vector<int>(arr.size(),0));
	int distance = getDistance(arr);
	int temp = 1;
	int round = 1;//控制键值排序依据在哪一位
	while (round <= distance) {
		// 用来计数：数组counter[i]用来表示该位是i的数的个数
		vector<int> counter(10,0);
		// 将array中元素分布填充到bucket中，并进行计数
		for (int i = 0; i < arr.size(); i++) {
			int which = (arr[i] / temp) % 10;
			buckets[which][counter[which]] = arr[i];
			counter[which]++;
		}
		int index = 0;
		// 根据bucket中收集到的arr中的元素，根据统计计数，在arr中重新排列
		for (int i = 0; i < 10; i++) {
			if (counter[i] != 0) {
				for (int j = 0; j < counter[i]; j++) {
					arr[index] = buckets[i][j];
					index++;
				}
			}
			counter[i] = 0;
		}
		temp *= 10;
		round++;
	}
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54

稳定性
通过上面的排序过程，我们可以看到，每一轮映射和收集操作，都保持从左到右的顺序进行，如果出现相同的元素，则保持他们在原始数组中的顺序。可见，基数排序是一种稳定的排序。

适用场景
基数排序要求较高，元素必须是整数，整数时长度10W以上，最大值100W以下效率较好，但是基数排序比其他排序好在可以适用字符串，或者其他需要根据多个条件进行排序的场景，例如日期，先排序日，再排序月，最后排序年 ，其它排序算法可是做不了的。

总结

img

平均时间复杂度来说：

快速排序、堆排序、归并排序都是 O ( n log ⁡ 2 n ) O(n\log_2n) O(nlog2​n)

说明：

当原表有序或基本有序时，直接插入排序和冒泡排序将大大减少比较次数和移动记录的次数，时间复杂度可降至O（n）；

而快速排序则相反，当原表基本有序时，将蜕化为冒泡排序，时间复杂度提高为 O （ n 2 ） O（n^2） O（n2）；

原表是否有序，对简单选择排序、堆排序、归并排序和基数排序的时间复杂度影响不大。

稳定性：

排序算法的稳定性:若待排序的序列中，存在多个具有相同关键字的记录，经过排序， 这些记录的相对次序保持不变，则称该算法是稳定的；若经排序后，记录的相对 次序发生了改变，则称该算法是不稳定的。
稳定性的好处：排序算法如果是稳定的，那么从一个键上排序，然后再从另一个键上排序，第一个键排序的结果可以为第二个键排序所用。基数排序就是这样，先按低位排序，逐次按高位排序，低位相同的元素其顺序再高位也相同时是不会改变的。另外，如果排序算法稳定，可以避免多余的比较；

稳定的排序算法：冒泡排序、插入排序、归并排序、计数排序、桶排序和基数排序

不是稳定的排序算法：选择排序、快速排序、希尔排序、堆排序

选择排序算法的依据

1.待排序的记录数目n的大小；

2．记录本身数据量的大小，也就是记录中除关键字外的其他信息量的大小；

3．关键字的结构及其分布情况；

4．对排序稳定性的要求。

设待排序元素的个数为n.

1）当n较大，则应采用时间复杂度为O(nlog2n)的排序方法：快速排序、堆排序或归并排序。

  • 快速排序：是目前基于比较的内部排序中被认为是最好的方法，当待排序的关键字是随机分布时，快速排序的平均时间最短；
  • 堆排序 ： 如果内存空间允许且要求稳定性的
  • 归并排序：它有一定数量的数据移动，所以我们可能过与插入排序组合，先获得一定长度的序列，然后再合并，在效率上将有所提高。

2） 当n较大，内存空间允许，且要求稳定性 =》归并排序

3）当n较小，可采用直接插入或直接选择排序。

  • 直接插入排序：当元素分布有序，直接插入排序将大大减少比较次数和移动记录的次数。

  • 直接选择排序 ：元素分布有序，如果不要求稳定性，选择直接选择排序

4）一般不使用或不直接使用传统的冒泡排序。

5）基数排序
它是一种稳定的排序算法，但有一定的局限性：
　　1、关键字可分解。
　　2、记录的关键字位数较少，如果密集更好
　　3、如果是数字时，最好是无符号的，否则将增加相应的映射复杂度，可先将其正负分开排序。

  • 元素的移动次数与关键字的初始排列次序无关的是：基数排序
  • 元素的比较次数与初始序列无关是：选择排序、折半插入排序
  • 算法的时间复杂度与初始序列无关的是：选择排序、堆排序、归并排序、基数排序
  • 算法的排序趟数与初始序列无关的是：插入排序、选择排序、基数排序

参考：

https://zhuanlan.zhihu.com/p/42586566

https://blog.csdn.net/FISHBALL1/article/details/52425521

https://cshihong.github.io/2019/02/27/10%E7%A7%8D%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95%E7%9A%84%E5%AF%B9%E6%AF%94%E5%88%86%E6%9E%90/

https://blog.csdn.net/qi_700/article/details/77193805

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/盐析白兔/article/detail/278092
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号