很楠不爱3

这个屌丝很懒，什么也没留下！

热门标签

【转】十大经典排序算法最强总结_十大经典排序算法最强组合

作者：很楠不爱3 | 2024-02-29 05:47:20

踩

十大经典排序算法最强组合

参考文献

参考地址1
参考地址2
参考地址3

在这里插入图片描述

1.冒泡排序

思路：比较相邻的元素。如果第一个比第二个大，就交换它们两个；对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数；针对所有的元素重复以上的步骤，除了最后一个；
时间复杂度：O(n²)
空间复杂度：原址排序
是否稳定：是
应用场景：优化后的冒泡排序可用于当数据已经基本有序，且数据量较小时。
优化措施：设置一个标志，每轮比较时，如果发现没有进行交换操作，说明数组已经有序，退出循环，停止比较。
在这里插入图片描述

int* BubbleSort(int array[])
{
	if(array.length()==0)
		return array;
	for(int i=0;i<array.length()-1;i++)    //-1是因为它是双下标策略里的前一个下标，因此访问不到最后一个元素；
	{
		for(int j=i+1;j<array.length()-i-1;j++)       //注意这里的边界条件！！
		{
			if(array[i]<array[j])
			{	
				int temp=array[j];
				array[j]=array[i];
				array[i]=temp;
			}
		}
	}
	return array;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

2.选择排序

思路：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

时间复杂度：O(n²)
空间复杂度：原址排序
是否稳定：否
应用场景：当数据规模较小时，选择排序性能较好
优化措施：每次寻找最小或最大元素时，同时记录最小最大元素的位置，每次使用3次比较寻找两个元素的位置，而不是4次比较
在这里插入图片描述

int* SelectionSort(int array[])
{
	if(array.length()==0)
		return array;
	for(int i=0;i<array.length();i++)
	{
		int min_index=i;                            //快慢指针策略思想的体现，min_index一直记录有序元素的下标；
		for(int j=i+1;j<array.length();j++)
		{
			if(array[j]<array[min_index])
				min_index=j;
		}                             //找到后面无序数中的最小元素；
		int temp=array[i];            //通过交换做一个移动；
		array[i]=array[min_index];
		array[min_index]=temp;
	}
	return array;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

3.插入排序

思路：从第一个元素开始，该元素可以认为已经被排序；取出下一个元素，在已经排序的元素序列中从后向前扫描；
如果该元素（已排序）大于新元素，将该元素移到下一位置；重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；将新元素插入到该位置后；重复步骤2~5。

时间复杂度：O(n²)
空间复杂度：原址排序
是否稳定：是
应用场景：若数组基本有序且数据规模较小时，选用插入排序较好.
优化措施：由于每次插入是向已排序数组中插入，可使用二分查找查找到相应位置进行插入
在这里插入图片描述
01.循环版本

int* InsertSort(int array[])
{
	if(array.length()==0)
		return array;
	for(int i=0;i<array.length();i++)
	{
		int temp=array[i+1];                  //先把本轮这个要排序的元素备份起来；
		int index=i;                          //然后从该位置向前查找有序元素集合；
		while(index>=0 && temp<array[index])  //这种查找不是访问，而是不断把前面的元素往后移动，直到找到合适的插入位置；
		{
			array[index+1]=array[index];
			index--;
		}
		array[index+1]=temp;
	}
	return array;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

02.递归版本

void insertSort(int arr[], int n)
{
	if(n == 0)
		return;
	insertSort(arr, n - 1);
	int i = n - 1;
	int key = arr[n];
	while(i >= 0 && arr[i] > key)
	{
		arr[i + 1] = arr[i];
		i--;
	}
	arr[i + 1] = key;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

4.希尔排序

思路：希尔排序也是一种插入排序，它是简单插入排序经过改进之后的一个更高效的版本。通过迭代缩小gap值（这个gap就是分的组数），使得数组从小分组的排序逐渐合并为大分组的合并。

时间复杂度：小于O(n^4/3)
空间复杂度：原址排序
是否稳定：否
注：对于希尔排序涉及到一个增量步长的选择，具体选择标准可参照WIKI Gap_sequence
应用场景：数据量较小且基本有序时
在这里插入图片描述

int * ShellSort(int array[])
{
	int len=array.length();
	int temp;
	int gap=len/2;
	
	while(gap>0)
	{
		for(int i=gap; i<len; i++)
		{
			temp=array[i];
			int preindex=i-gap;
			while(preindex>=0 && array[preindex]>temp)             //后与前比较
			{
				array[preindex+gap]=array[preindex];
				preindex -=gap;
			}
			array[preindex+gap]=temp;
		}
		gap /=2;
	}
	return array;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

5.归并排序

思路：该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。
把长度为n的输入序列分成两个长度为n/2的子序列；对这两个子序列分别采用归并排序；将两个排序好的子序列合并成一个最终的排序序列。（这里的划分属于递归部分，即最底层是从两个数的排序起步，逐步向上合并）

时间复杂度：O(nlogn)
空间复杂度：O(n)
是否稳定：是
应用场景：数据量较大且要求排序稳定时
优化措施：由于使用递归，递归深度太深容易造成内存溢出，所以可使用非递归版本归并排序
在这里插入图片描述

#include <iostream>
#include <vector>
using namespace std;
 
void merge(vector<int>& A, vector<int> L, vector<int> R) {
    int l = L.size();
    int r = R.size();
    int i = 0;
    int j = 0;
    int k = 0;
    while(i < l && j < r) {
        if(L[i] < R[j]) {
            A[k++] = L[i++];
        } else {
            A[k++] = R[j++];
        }
    }
    while(i < l) A[k++] = L[i++];
    while(j < r) A[k++] = R[j++];
}
 
void mergesort(vector<int>& arr) {
    int n = arr.size();
    if(n < 2) return;
    int mid = n/2;
    int i;
    vector<int> L(mid);
    vector<int> R(n - mid);
    for(i = 0; i < mid; ++i) {
        L[i] = arr[i];
    }
    for(;i < n; ++i) {
        R[i-mid] = arr[i];
    }
    mergesort(L);
    mergesort(R);
    merge(arr, L, R);
}
 
int main() {
    int arr[10] = {2, 5, 4, 3, 1, 6, 8, 9, 7, 0};
    vector<int> Arr(arr, arr + 10);
    for(int i = 0; i < 10; ++i)
        cout << Arr[i] << " ";
    cout << endl;
    mergesort(Arr);
    for(int i = 0; i < 10; ++i)
        cout << Arr[i] << " ";
    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
49
50
51

6.快速排序

思路：通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。

具体来说，快排的实现还是很有讲究的。partition作为核心函数，它的实现思路是：
step1.每次随机一个下标，然后把这个下标位置的数放到数组末端，这样数组在遍历的时候一直是和最后位置的数进行的比较；
step2.用一个smallindex值统计该数组中比这个随机指定的数小的数的数目，统计思路就是，在遍历过程中，如果说smallindex不等于遍历的 i 了，那么说明之前轮中出现了比随机值大的数，因此就需要把这一轮比这个随机数小的数和之前轮中比随机数大的数进行交换，这样使得前smallindex的数一直是小于这一随机数的。

时间复杂度：O(nlogn)
空间复杂度：原址排序
是否稳定：否
应用场景：快速排序适合处理大量数据排序时的场景
优化措施：由于如果每次选取基准元素时都选到了最小或最大的元素，会导致快排时间复杂度很高，所以可以随机选取基准元素，能有效的提高排序的平均性能，防止时间复杂度达到O(n²)。

在这里插入图片描述

int partition(vector<int>&array, int left, int right)
{
    if(right-left < 1)
        return -1;
    int key=array[right];       //直接用最右边的数作为比较的数
    int small=left;             //small用于标记下标，在其左侧的都是小于key值的元素
    for(int i=left;i<right;i++)
    {
        if(array[i]<key)
            swap(array[i],array[small++]);
    }
    swap(array[right],array[small]);  //把比较的数放回合适的位置，这样其左边就都是小于它的值，右边都是大于它的值
    return small;                     //返回该比较数的下标
}

void quicksort(vector<int> &array, int left, int right)
{
	if(left == right)
		return;
    if(left<right)
    {
        int i = partition(array, left, right);
        if(i!=-1)
        {
            quicksort(array,left,i-1);
            quicksort(array,i+1,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

7.堆排序

参考博客——图示做的很清晰直观！

堆的相关概念：

【1】堆是一个完全二叉树；
【2】完全二叉树即是：若设二叉树的深度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第 h 层所有的结点都连续集中在最左边，这就是完全二叉树。
【3】堆满足两个性质：堆的每一个父节点数值都大于（或小于）其子节点，堆的每个左子树和右子树也是一个堆。
堆分为最小堆和最大堆。最大堆就是每个父节点的数值要大于孩子节点，最小堆就是每个父节点的数值要小于孩子节点。排序要求从小到大的话，我们需要建立最大堆，反之建立最小堆。
【4】堆的存储一般用数组来实现。假如父节点的数组下标为 i 的话，那么其左右节点的下标分别为：(2i+1)和 (2i+2)。如果孩子节点的下标为 j 的话，那么其父节点的下标为 (j-1)/2。
【5】完全二叉树中，假如有n个元素，那么在堆中最后一个父节点位置为(n/2-1)

在这里插入图片描述
思路：将初始待排序关键字序列(R1,R2….Rn)构建成大顶堆，此堆为初始的无序区；将堆顶元素R[1]与最后一个元素R[n]交换，此时得到新的无序区(R1,R2,……Rn-1)和新的有序区(Rn),且满足R[1,2…n-1]<=R[n]；由于交换后新的堆顶R[1]可能违反堆的性质，因此需要对当前无序区(R1,R2,……Rn-1)调整为新堆，然后再次将R[1]与无序区最后一个元素交换，得到新的无序区(R1,R2….Rn-2)和新的有序区(Rn-1,Rn)。不断重复此过程直到有序区的元素个数为n-1，则整个排序过程完成。

时间复杂度：O(nlog(n))
空间复杂度：原址排序
是否稳定：否
应用场景：堆排序适合处理数据量大的情况，数据呈流式输入时用堆排序也很方便
优化措施：建立堆的时候不需要对叶子结点进行维护堆性质操作，因此只需要对n/2个数进行维护堆操作
在这里插入图片描述

//代码参考地址：https://www.cnblogs.com/zeze/p/9488239.html
public class HeapSort {
    private static void sort(int[] arr) 
    {     
        // 1、构建大顶堆
        for(int i=arr.length/2-1;i>=0;i--)
            adjustHeap(arr,i,arr.length);   //从第一个非叶子节点从下至上，从右至左调整结构
        
        //2、调整堆结构+交换堆顶元素与末尾元素
        for(int j=arr.length-1; j>0; j--)
        {
            swap(arr,0,j);                  //将堆顶元素与末尾元素进行交换
            adjustHeap(arr, 0, j);          //重新对堆进行调整
        }
    }
    
    private static void swap(int[] arr, int a, int b)
    {
        int temp=arr[a];
        arr[a] = arr[b];
        arr[b] = temp;
    }
 
    private static void adjustHeap(int[] arr, int i, int length) 
    {
        int temp=arr[i];
        for(int k=i*2+1;k<length;k=k*2+1)
        {                                  //从i结点的左子结点开始，也就是2i+1处开始
            if(k+1<length && arr[k]<arr[k+1])
                k++;
            if(arr[k]>temp)
            {                              //如果子节点大于父节点，将子节点值赋给父节点（不用进行交换）
                arr[i]=arr[k];
                i=k;
            }
            else
                break;
        }
        arr[i]=temp;                       //将temp值放到最终的位置
    }
}
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

8.计数排序

思路：计数排序使用一个额外的数组C，其中第i个元素是待排序数组A中值等于i的元素的个数。然后根据数组C来将A中的元素排到正确的位置。它只能对整数进行排序。（其实就是一种简单的计数方法，需要用到额外内存空间）

时间复杂度：O(n)
空间复杂度：O(n)+O(N)
是否稳定：是
应用场景：计数排序虽然时间复杂度较低，但需要满足的条件较多，如果能满足限制条件与空间需求，计数排序自然很快
优化措施：为了保障稳定性，算法中进行了多余的操作，如果不需要稳定性，可以优化时间。

在这里插入图片描述

void CountSort(vector<int>& array, int max_num)
{
    int len=array.size();
    if(len==0)
        return;
    vector<int> extra_array(max_num+1);
    for(int i=0;i<len;i++)
        extra_array[array[i]]++;
    for(int i=1;i<=max_num;i++)
        extra_array[i]=extra_array[i]+extra_array[i-1];
    
    vector<int> copyarr;
    copyarr.assign(array.begin(),array.end());
    for(int i=len-1;i>=0;i--)
    {
        array[extra_array[copyarr[i]]-1]=copyarr[i];
        extra_array[copyarr[i]]--;
    }
    //这是我自己的想法，好像比较直观。。。
    // int index=0;
    // for(int i=1;i<=max_num;i++)
    // {
    //     for(int j=0;j<extra_array[i];j++)
    //         array[index++]=i;
    // }
    return;
}
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

9.桶排序

思路：桶排序是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。
假设输入数据服从均匀分布，将数据分到有限数量的桶里，每个桶再分别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序。

时间复杂度：O(n)
空间复杂度：O(n)
是否稳定：是
应用场景：如果满足桶排序的假设条件，那么桶排序的速度是非常快的
在这里插入图片描述

void BucketSort(vector<int>& array,int max_num)
{
    int len=array.size();
    if(len==0)
        return;
    int radix=1;
    while(radix<max_num)
        radix*=10;
    
    int idx=0;
    vector<vector<int>> bucket(len);
    for(int i=0;i<len;i++)
    {
        idx=len*(array[i]/(double)radix);
        bucket[idx].push_back(array[i]);
    }
    idx=0;
    for(int i=0;i<len;i++)
    {
        sort(bucket[i].begin(),bucket[i].end());
        if(!bucket.empty())
        {
            for(int j=0;j<bucket[i].size();j++)
            {
                array[idx]=bucket[i][j];
                idx++;
            }
        }
    }
    return;
}
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

10.基数排序

思路：基数排序是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。
具体的：
step1.先取得数组中的最大数，并由此取得位数；
step2. arr为原始数组，从最低位开始取每个位组成radix数组；
step3.对radix进行计数排序（利用计数排序适用于小范围数的特点）；

时间复杂度：O(n)
空间复杂度：O(n)
是否稳定：是
应用场景：同计数排序
在这里插入图片描述

/*基数排序*/
void RadixSort(vector<int>& arr, int max_elem) {
    int len = arr.size();
    if (len == 0)
        return;
    int exp_max = 1;
    int radix = 10;                     //十进制序列
    while (max_elem / exp_max > 0)
        exp_max *= radix;
    int exp = 1;
    vector<int> countArr(radix);
    vector<int> exchangeArr;
    exchangeArr.assign(arr.begin(), arr.end());
    while (exp < exp_max) {
        for (int i = 0; i < len; i++)
            countArr[(exchangeArr[i] / exp) % radix]++;
        for (int i = 1; i < radix; i++)
            countArr[i] = countArr[i] + countArr[i - 1];
        for (int i = len - 1; i >= 0; i--) {
            int tmp = countArr[(exchangeArr[i] / exp) % radix] - 1;
            arr[countArr[(exchangeArr[i] / exp) % radix] - 1] = exchangeArr[i];
            countArr[(exchangeArr[i] / exp) % radix]--;
        }
        exchangeArr.assign(arr.begin(), arr.end());
        countArr.assign(radix, 0);
        exp *= radix;
    }
    return;
}

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

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/很楠不爱3/article/detail/163966