算法概述

常见的排序算法

  • 冒泡排序
  • 选择排序
  • 插入排序
  • 归并排序
  • 快速排序
  • 堆排序
  • 基数排序(非比较类算法)

算法复杂度

image.png

相关概念

  • 稳定：如果 a 原本在 b 前面，而 a=b，排序之后 a 仍然在 b 的前面。
  • 不稳定：如果 a 原本在 b 的前面，而 a=b，排序之后 a 可能会出现在 b 的后面。
  • 时间复杂度：对排序数据的总的操作次数。反映当 n 变化时，操作次数呈现什么规律。
  • 空间复杂度： 是指算法在计算机内执行时所需存储空间的度量，它也是数据规模 n 的函数

冒泡排序

算法描述

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

动画演示

33a947c71ad62b254cab62e5364d2813.gif

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
//冒泡排序算法  
void bubble_sort(ElemType arr[],int n){  
    int i,j;  
    bool flag;  //用来标记是否发生了交换
    for(i=0;i<n-1;i++){//外层循环需要比较n-1次  
        flag=false;  
        for(j=n-1;j>i;j--){//内层循环  
            if(arr[j]<arr[j-1]){  
                swap(arr[j],arr[j-1]);  
                flag=true;//有交换就返回true  
            }  
        }  
        if(flag==false){//如果这一趟没有比较，直接结束无须比较  
            return;  
        }  
    }  
}

选择排序

算法描述

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

动画演示

1c7e20f306ddc02eb4e3a50fa7817ff4.gif

代码实现

1
2
3
4
5
6
7
8
9
10
11
void SelectSort(ElemType A[],int n)(
	for(int i=0;i<n-1;i++){   //一共进行n-1趟			
		int min=i;        //记录最小元素位置  
		for(int j=i+l;j<n;j++){      //在A[i.n-1]中选择最小的元素
			if (A[j]<A(min]){  
				min=j;              //更新最小元素位置
			}
		}
		swap(A(i],A[min]);  
	} 
}

算法分析

是一种不稳定算法 例如举个例子，序列arr = [5 8 5 2 9]，我们知道第一遍选择第1个元素5会和2交换，那么原序列中两个5的相对前后顺序就被破坏了，所以选择排序是一个不稳定的排序算法。却是表现最稳定的排序算法之一，因为无论什么数据进去都是 O(n2)的时间复杂度，所以用到它的时候，数据规模越小越好。唯一的好处可能就是不占用额外的内存空间了吧。理论上讲，选择排序可能也是平时排序一般人想到的最多的排序方法了吧。

插入排序

算法描述

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

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

动画演示

91b76e8e4dab9b0cad9a017d7dd431e2.gif

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
//插入排序方法  
void insert_sort(ElemType *str,int n){ //n为数组长度 
    int i,j,temp;  
    for(i=1;i<n;i++){  
        temp=str[i];//暂时存目标元素  
        for(j=i-1;j>=0&&str[j]>temp){//将比插入的数大的全部往后移一格  
            str[j+1]=str[j];  
            j--;
        }  
        str[j+1]=temp;//j来到了插入位置，将temp插入  
    }  
}

算法分析

是一种稳定的排序算法，插入排序在实现上，通常采用 in-place 排序（即只需用到 O(1)的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。

归并排序

算法描述

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

  • 把长度为 n 的输入序列分成两个长度为 n/2 的子序列；
  • 对这两个子序列分别采用归并排序；
  • 将两个排序好的子序列合并成一个最终的排序序列。

动画演示

cdda3f11c6efbc01577f5c29a9066772.gif

代码实现

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
int *B=(int *)malloc(n*sizeof(int));//辅助数组B

void Merge(int A[],int low,int high,int mid){
	int i,j,k;
	for(k=low;k<high;k++){
		B[k]=A[k];
	}
	for(i=low,j=mid+1,k=i;i<=mid&&j<=high;k++){
		if(B[i]<=B[j]){
			A[k]=B[i];
			i++;
		}else{
			A[k]=B[j];
			j++;
		}
	}
	while(i<=mid){
		A[k++]=B[i++];
	}
	while(j<=high){
		A[k++]=B[j++];
	}
}

void MergeSort(int A[],int low,int high){
	if(low<=high){
		int mid=(low+high)/2;
		MergeSort(A,low,mid);  //不断递归的左右划分
		MergeSort(A,mid+1,high);
		Merge(A,low,mid,high); //归并
	}
}

算法分析

归并排序是一种稳定的排序方法。和选择排序一样，归并排序的性能不受输入数据的影响，但表现比选择排序好的多，因为始终都是 O(nlogn）的时间复杂度。代价是需要额外的内存空间。

快速排序

算法描述

快速排序的基本思想：通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。
快速排序使用分治法来把一个串（list）分为两个子串（sub-lists）。具体算法描述如下：

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

动画演示

GIF 2023-10-28 15-46-31.gif

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int partition(int A[],int low,int high）{ //一趟划分
	int pivot=A[low]：//将当前表中第一个元素设为枢轴，对表进行划分
	while（low<high）{ //循环跳出条件
		while(low<high&&A[high]>=pivot)
			--high；
		A[low]=A[high]； //将比框轴小的元素移动到左端
		while(low<high&&A[low]<=pivot)
			++low；
		A[high]=A[low] //将比框轴大的元素移动到右端
	}
	A[low]=pivot //框轴元素存放到最终位置
	return low； //返回存放枢轴的最终位置

//快速排序方法  
void Q_sort(int *str,int low,int high){  
    if(low<high) {//low high用来限定分割的范围  
        int postion = partition(str, low, high);
        //partition方法是核心方法，每一次分割的方法  
        Q_sort(str, low, postion - 1);//递归左边的数组  
        Q_sort(str, postion + 1, high);//递归数组右边  
    }  
    return;
}

算法分析

快速排序是一种不稳定算法，快速排序算法的最坏情况是数据元素已全部有序，此时数据元素数组的根结点的分需次数构成一棵二叉退化树(即单分支二叉树),一棵二叉退化树的深度是 n.所以最坏情况下快速排序算法的时间复杂度为 O(n2)。般情况下.标准元素值的分布是随机的,这样的二支树的深度接近于 log2n,所以快速排序算法的平均(或称期望)时间复杂度为 O(nlog2n)

希尔排序

算法描述

1959年Shell发明，第一个突破O(n2)的排序算法，是简单插入排序的改进版。它与插入排序的不同之处在于，它会优先比较距离较远的元素。希尔排序又叫缩小增量排序

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

动画演示

GIF 2023-11-2 18-19-47.gif

算法分析

希尔排序时不稳定算法，希尔排序的核心在于间隔序列的设定。既可以提前设定好间隔序列，也可以动态的定义间隔序列。

堆排序

算法描述

堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。

  • 将初始待排序关键字序列(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，则整个排序过程完成。

动画演示

7073c729230e1a2c3c3c9207b25f6b43.gif

算法分析

堆排序是一种不稳定排序算法，对于 n 个元素的序列，构造堆过程，需要遍历的元素次数为 O(n)，每个元素的调整次数为 O(log2n)，所以构造堆复杂度为 O(nlog2n)。迭代替换待排序集合首尾元素的次数为 O(n)，每次替换后调整次数为 O(log2n)，所以迭代操作的复杂度为 O(nlog2n)。由此可知堆排序的时间复杂度为 O(nlog2n)，排序过程属于原地排序，不需要额外的存储空间，所以空间复杂度为 O(1)。

基数排序

算法描述

基数排序是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。有时候有些属性是有优先级顺序的，先按低优先级排序，再按高优先级排序。最后的次序就是高优先级高的在前，高优先级相同的低优先级高的在前。

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

动画演示

3a6f1e5059386523ed941f0d6c3a136e.gif

算法分析

基数排序时一种稳定的排序算法，在每一位的排序过程中，基数排序使用稳定的排序算法（通常是桶排序或计数排序）来保持相同关键字的相对顺序。在分配和收集的过程中，相同关键字的元素会被依次放入相应的桶中，并在下一轮排序时按照桶的顺序被取出。这就确保了在同一位上相同元素的相对顺序保持不变。