每天进步一点点

0%

排序算法总结

发表于 更新于 阅读次数： ℃ Valine：
本文字数： 5.9k 阅读时长 ≈ 10 分钟
常使用的排序方法总结

 数据结构中常用的排序方法主要有以下几种：

  • 冒泡排序

  • 快速排序

  • 希尔排序

  • 堆排序

  • 直接选择排序

  • 直接插入排序

  • 归并排序

下面分别对其介绍，总体可以分为三类：

排序LowB三人组：冒泡排序，选择排序，插入排序

排序NB三人组：快速排序，堆排序，归并排序

其他排序：希尔排序，计数排序，归并排序

0、引子

这里给出了七种排序算法，根据清华大佬的总结分类可以大致分为三类

1、冒泡排序

 冒泡排序是接触排序算法以来最经常使用的排序算法，两两比较相邻数据，如果反序则交换，直到没有反序记录为止。外层循环一次会将最大的值移到最右边，二次将次大值移到最右边。

a.程序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void BobuleSort(vector<int> &array)
{
	for (int i = 0; i < array.size() - 1; i++)
	{
		for (int j = 0; j < array.size() - 1 - i; j++)
		{
			if (array[j+1] < array[j])
			{
				int temp = array[j+1];
				array[j+1] = array[j];
				array[j] = temp;
			}
		}
	}
}

b.复杂度分析

 冒泡排序的时间复杂度最简单的情况是原本就是一个递增的数组，比较（n-1）次。最复杂的情况为逆序数组，比较次数为1+2+…+(n-1)+n次，所以时间复杂度为n*(n-1)/2。

c.冒泡排序的算法改进

 冒泡排序存在某一趟遍历过程中并没有发生任何交换的情况，这时可以在每一趟开始前先定义一个状态exchange为false,如果在一趟中存在交换，则将exchange改为true。

​ 然后在每一趟结束后就可以进行判断exchange，如果还是为false就说明以已经有序，可以结束了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void BobuleSort(vector<int> &array)
{
	for (int i = 0; i < array.size() - 1; i++)
	{
        bool exchange=false;
		for (int j = 0; j < array.size() - 1 - i; j++)
		{
			if (array[j+1] < array[j])
			{
                  exchange=true;
				int temp = array[j+1];
				array[j+1] = array[j];
				array[j] = temp;
			}
		}
         if(!exchange) break;
	}
}

2、快速排序

 快速排序最核心的地方在于找到中轴值，小于中轴在左边，大于中轴在右边，右左交替判断，满足继续移动，不满足换左右，排完然后递归进行。快速排序使用到了递归的思想。

a.程序

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
//快速排序算法研究：中心轴数据，小于中心轴在左侧，大于中心轴在右侧，递归执行
void Quick_Sort(vector<int> &Array, int L, int R)
{
	if (L >= R) return;
	int left = L, right = R;
	int pivot = Array[left];
	while (left < right)
	{
		//先看最右边，最右边大于中心轴数据则继续往次右边移动
		while (left < right&&Array[right]>=pivot)
		{
			right--;
		}
		//右边数据小于了中心轴数据，将右边数据给中心轴位置
		if (left < right)
		{
			Array[left] = Array[right];
		}

		//左边数据一定要小于中心轴数据
		while (left < right && Array[left] <= pivot)
		{
			left++;
		}
		//左边数据大于了中心轴数据
		if (left < right)
		{
			Array[right] = Array[left];//刚才此位置数据已经小于中心轴数了，现在给他找了一个大于中心轴数的人
		}

		//左右在这里相遇了，中轴数据已经被提溜出来了，现在只需要把中心轴数据放在相遇位置
		if (left >= right)
		{
			Array[left] = pivot;
		}

		//此时左变全部小于中轴，右边全部大于中轴，左右使用同样的方法再次进行排序
		Quick_Sort(Array, L, right - 1);
		Quick_Sort(Array, right + 1, R);
	}
}

上面的代码不够直观，我自己又写了一个更加直观的方法，主要是利用partition函数来找到中间的那个可以分割左右的下标。

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
#include<iostream>
#include<vector>
using namespace std;
void Print(vector<int>& nums)
{
    for(auto c:nums) cout<<c<<" ";
    cout<<endl;
}
//partition函数的意思是分割，割断的意思
int partition(vector<int>& nums,int left,int right)
{
    int mid=nums[left];
    while(left<right){
        //从右边分析，若是右边有小于pivot的数字，将其放在左边
        while(left<right&&nums[right]>=mid) right--;
        if(left<right) nums[left]=nums[right];
        //切换到左边，若是左边有大于pivot的值，将其放在右边。
        while(left<right&&nums[left]<=mid) left++;
        if(left<right) nums[right]=nums[left];
    }
    nums[left]=mid;
    return left;
}
void QuickSort(vector<int>& nums,int L,int R)
{
    if(L<R)
    {
        int pivot=partition(nums,L,R);
        QuickSort(nums,L,pivot-1);
        QuickSort(nums,pivot+1,R);
    }
}

int main()
{
    vector<int> nums;
    nums.push_back(12);
    nums.push_back(4);
    nums.push_back(8);
    nums.push_back(6);
    nums.push_back(9);
    nums.push_back(0);
    int len=nums.size();
    QuickSort(nums,0,len-1);
    Print(nums);
    system("pause");

}

b.复杂度分析

快速排序的时间复杂度为nlongn,空间复杂度的话，主要是递归造成的栈空间的使用，最好的情况递归深度为log2N其空间复杂度为logn

3、希尔排序

1、分组

找到一定的间隔，每个间隔内N个元素为一组，然后对每一个子序列进行直接插排序。

希尔排序和直接插入排序关系密不可分。

2、每一组的组内进行排序

组内排好序后，重新设定一个间隔，重新设的间隔为第一次分组的一半。下一次在进行减小一般，直至最后为1。

4、堆排序

堆的概念 ：堆是数据结构中二叉树的一种类型，一种特殊的二叉树。根节点（亦称为堆顶）的关键字是堆里所有节点关键字中最大者，称之为大根堆，大根堆要求根节点的关键字即大于等于左子树的关键字值又大于等于右子树的关键字值。

堆的向下调整性质：假设根节点的左右子树都是堆，但根节点不满足堆的性质，可通过一次向下调整将其变成一个堆。

堆的调整与构造：农村包围城市，先从最后一个非叶子节点进行二叉树的考虑。

堆排序过程：堆排序的优质文章

  1. 构造一个大顶堆，取堆顶数字（也就是最大值）
  2. 再将剩下的数字构造一个大顶堆，取堆顶数字（也就是剩下所有元素的最大值）
  3. 重复以上操作，直到取完堆中的数字，最终得到一个从大到小的排序序列
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
55
56
57
58
59
60
61
62
package sortdemo;

import java.util.Arrays;

/**
 * Created by chengxiao on 2016/12/17.
 * 堆排序demo
 */
public class HeapSort {
    public static void main(String []args){
        int []arr = {9,8,7,6,5,4,3,2,1};
        sort(arr);
        System.out.println(Arrays.toString(arr));
    }
    public 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);//重新对堆进行调整
        }

    }

    /**
     * 调整大顶堆（仅是调整过程，建立在大顶堆已构建的基础上）
     * @param arr
     * @param i
     * @param length
     */
    public static void adjustHeap(int []arr,int i,int length){
        int temp = arr[i];//先取出当前元素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指向右子结点
                k++;
            }
            if(arr[k] >temp){//如果子节点大于父节点，将子节点值赋给父节点（不用进行交换）
                arr[i] = arr[k];
                i = k;
            }else{
                break;
            }
        }
        arr[i] = temp;//将temp值放到最终的位置
    }

    /**
     * 交换元素
     * @param arr
     * @param a
     * @param b
     */
    public static void swap(int []arr,int a ,int b){
        int temp=arr[a];
        arr[a] = arr[b];
        arr[b] = temp;
    }
}

堆排序的平均复杂度：O(N*logN)

5、直接选择排序

a.直接插入排序思想

主要思想为，对于一个乱序数组，我们首先从全部里面找到一个最小的放在最前面，然后从剩下的里面找到一个最小的再放到次前面，最后得到一个有序的数组。

  • 从下标零开始，同时需要记忆min_i和min_value。
  • 如果发现后面的值小于当前，则就需要交换。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void Select_sort(vector<int> nums,int len)
{
    int i,j;
    int min_value,min_pos;
    for(i=0;i<len-1;i++)
    {。
        min_pos=i;
        //下面循环负责找i后面最小值及其位置
        for(j=i+1;j<len;j++)
        {
            if(nums[j]<min_value) min_pos=j;
        }
        //将i后面最小值及其位置给换到i的位置上，首先最小值位置先把i给扔过去
        int temp=nums[i];
        nums[i]=nums[min_pos];
        nums[min_pos]=temp;
    }
}

b.时间复杂度分析

这个算法的复杂度显而易见，时间复杂度为O（n^2）;

6、直接插入排序

a.插入排序思路

直接插入排序就是我们经常玩扑克牌时多用的方法，每一次我们都认为我们当前的排序是有序的，然后下一个元素进来时，我们通过插入排序将其放入指定的位置，当最后一个元素放完时，插入排序也就结束了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void insert_sort(vector<int>& a,int len)
{
    int value;
    for(int i=1;i<len;i++)
    {
        //从第一个元素开始，去分析其后面一个元素：
        //若是其后元素小于前面一个元素，就将其插进去
        int temp=nums[i];
        int j=i-1;
        while(j>=0&&nums[j]>temp)
        {
            nums[j+1]=nums[j];
            j--;
        }
        nums[j+1]=temp;
    }
}

b. 时间复杂度分析

由于也是两个层大的循环，所以插入排序的时间复杂度为O(n^2)。

7、归并排序

  1. 将待排序序列中的数字分为若干组，每个数字为一组

  2. 将若干组两两合并，保证合并后的数组是有序的

  3. 重复进行第二步，最终得到排序后的一组

本文标题:排序算法总结

文章作者:Decaprio Lee

发布时间:2021年03月17日 - 09:03

最后更新:2021年05月31日 - 16:05

原始链接:http://yoursite.com/2021/03/17/027%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95%E6%80%BB%E7%BB%93/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。

赞赏一杯咖啡
-------------------本文结束 感谢您的阅读-------------------