文章详情

randy
2022-06-14
916
原创

数据结构之排序

1.冒泡排序

  • 核心思想:类似水泡一样,一趟比较,通过相邻元素的交换,冒出当前序列的最小值(最大值)到相应位置

  • 复杂度分析

    • 最好的情况:序列本身有序,只要进行n-1次比较,无需交换,时间复杂度为O(n)
    • 最差情况: 序列逆序,此时需要比较1+2+3+...(n-1)=n(n-1)/2次,并进行等数量级的交换
    • 辅助空间:O(1)
    • 综上,总的时间复杂度为O(n^2)

  • 稳定性:稳定

这里写图片描述

void bubbleSort(int arr[],int n){//冒泡排序 
	int flag=true;
	for(int i=0;i<n-1&&flag;i++){//flag作为标记,若有序,则不用瞎比较 
		flag=false;
		for(int j=n-1;j>=i;j--){//i+j=n-1
			if(arr[j]<arr[j-1]){
				swap(arr,j,j-1);
				flag=true; 
			}
		}
	}
}

2.简单选择排序

  • 核心思想:每一趟树立一个数作为靶子,谁比他小,就作为新靶子和剩下的比,最后的靶子就是这一趟最小的值了,然后除去这个数,再剩下的序列中重复此步骤即可

  • 复杂度分析

    • 比起冒泡,最大特点就是:交换移动数据相当少
    • 不管最好最差情况下,比较的次数都是一样多,而交换次数则有差别
    • 第i趟排序要进行n-i次关键字比较,比较次数为:n-1+n-2+...+1=n(n-1)/2次
    • 交换次数:
      • 最好的情况(有序):0次
      • 最差情况(逆序):n-1次
    • 辅助空间:O(1)
    • 最终时间复杂度为:O(n^2)

  • 稳定性:稳定

  • 性能比冒泡好点

#include <iostream>

void swap(int *&arr,int i,int j){
	int temp=arr[i];
	arr[i]=arr[j];
	arr[j]=temp;
} 

void simpleSort(int *arr,int n){//简单选择排序,在n-i+1个记录中选出最小关键字 
	int i,j,min;
	for(i=0;i<n;i++){//这里用i<n,当i=n-1时,j的条件不符,不会进入下一个for循环 
		min=i;
		for(j=i+1;j<n;j++){
			if(arr[min]>arr[j]){//这里必须要用arr[min],不能用arr[i] 
				min=j;
			}
		}
		if(min!=i){
			swap(arr,i,min);
		}
	}
}

void print(int *arr,int n){
	for(int i=0;i<n;i++){
		printf("%d ",arr[i]);
	}
}
int main(int argc, char** argv) {
	int arr[]={4,82,56,12,43,61,14};
	simpleSort(arr,7);
	print(arr,7);
	return 0;
}

3.直接插入排序

  • 核心思想:类似我们斗地主抓牌,第一张摸到直接放手里,第2张开始就要考虑手里的若干张牌的排列顺序了,第2张若比第1张小,则要把第2张放在第1张前面,现有的牌排好序后再抓第3张牌,然后依次比较第3张和第2张,第1张的大小关系,来决定第3张该摆在哪,依次类推,直到把抓到的最后一张牌排好序
  • 复杂度分析
  • 最好的情况(有序):0次移动,比较n-1次,时间复杂度为:O(n)
  • 最差(逆序):比较次数为:1+2+3+...+n-1=(n+2)(n-1)/2,移动次数也达到最大:(n+4)(n-1)/2次
  • 若排序记录随机,平均比较和移动次数约为:n^2/4
  • 辅助空间:O(1)
  • 总的复杂度为:O(n^2)
  • 稳定性:`稳定
  • 性能比冒泡和简单选择排序好点` 这里写图片描述
#include <iostream>

void swap(int *&arr,int i,int j){
	int temp=arr[i];
	arr[i]=arr[j];
	arr[j]=temp;
}

void InsertSort(int *arr,int n){//直接插入排序	
	int i,j;
	for(i=1;i<n;i++){//跟摸牌一样,摸到一张就和抓到手的牌比较,然后整理
		j=i;
		while(j>0&&arr[j]<arr[j-1]){//摸到的第一张和第0张比大小,排好序 
			swap(arr,j,j-1);//摸到第2张和第1张比大小,第1张和第0张比 
			j--;//摸到第3张和第2张比大小,第2张和第1张比大小,第1张和第0张比大小
		}
	}
}

void print(int *arr,int n){
	for(int i=0;i<n;i++){
		printf("%d ",arr[i]);
	}
}
int main(int argc, char** argv) {
	int arr[]={12,4,56,8,10,9,41};
	InsertSort(arr,7);
	print(arr,7); 
	return 0;
}

4.快速排序

  • 核心思想: 快速排序就是立一个数作为基准数,比他小的统统放左边,比他大的统统放在他的右边,接着通过递归,对它的左边序列,右边序列重复此过程,直到无数可分
  • 复杂度分析
  • 最好情况:O(nlogn)
  • 最差情况:O(n^2)
  • 平均情况:O(nlogn)
  • 辅助空间:O(logn)~O(n)
  • 稳定性:不稳定 ##图解## 如序列{6,1,2,7,9,3,4,5,10,8}

6作为基准数,左右安排两个哨兵i,j 这里写图片描述

哨兵i碰到比6小的就一路向右走(碰到比6大的就停下),哨兵j碰到比6大的,就一路向左走(碰到比6小的停下) 这里写图片描述 两者都停下时就进行交换,交换后的效果如下

这里写图片描述

接着两哨兵继续走, 这里写图片描述 两者都停下时便交换 这里写图片描述

直到两者相遇 这里写图片描述

此时可以选择和基准数交换位置 这里写图片描述

这里写图片描述 此时,以6为基准数的排序就完成了,接着以3为基准数重复此过程,再一下一个基准数重复,直到有序

完整过程如下图 完整排序过程如图 代码如下

#include <iostream>

void swap(int *&arr,int i,int j){
	int temp=arr[i];
	arr[i]=arr[j];
	arr[j]=temp;
}

int sortCore(int *arr,int start,int end){//快速排序 
	int i=start;
	int j=end;
	int temp=arr[start];
	while(i!=j){//定义两个一头一尾的哨兵 
		while(arr[j]>temp){//尾哨兵从后往前扫描,碰到比基准数大的就往前走 
			j--;
		}
		while(arr[i]<temp){//头哨兵从前往后扫,碰到比基准数小的往后走 
			i++;
		}
		swap(arr,i,j);
	}
	return i;
}

void quickSort(int *arr,int start,int end){
	int i;
	if(start<end){
		i=sortCore(arr,start,end);
		quickSort(arr,start,i-1);
		quickSort(arr,i+1,end);
	}
}
int main(int argc, char** argv) {
	int arr[]={2,23,54,12,13,64,7,10};
	quickSort(arr,0,7);
	for(int i=0;i<8;i++){
		printf("%d ",arr[i]);
	}
	return 0;
}

注:本文所用图均来自啊哈磊大神的博客

5. 希尔排序

  • 核心思想:其实就是直接排序的升级版,把序列按照一定的增量分组,各小组之间用直接排序的方法排好序,接着把增量缩小,重复此过程,直到最后增量为1
  • 复杂度分析:
  • 希尔排序是相隔某个增量的记录而组成的一个子序列,实现跳跃式的移动,使得效率提高
  • 迄今为止没找到最优的增长序列,但增量序列的最后一个值必须为1
  • 最好:O(n^3/2)
  • 最差:O(n^2)
  • 平均:O(nlogn)~O(n^2)
  • 时间复杂度为O(n^3/2),好于直接排序
  • 是第一个突破O(n^2)的排序算法
  • 辅助空间: 不稳定
  • 稳定性:不稳定

##图示## 这里写图片描述 代码如下

#include <iostream>

void swap(int *&arr,int i,int j){
	int temp=arr[i];
	arr[i]=arr[j];
	arr[j]=temp;
} 

void shellSort(int *arr,int n){//希尔排序,其实就是直接插入排序(摸牌)的进阶版 
	int i,j,increate;//把数组序列通过增量切分成多块,每一份中利用直接插入排序 
	for(increate=n/2;increate>0;increate/=2){
		for(i=increate;i<n;i++){//一个增量下排好序后就继续缩小增量,继续循环执行 
			j=i;
			while(j-increate>=0&&arr[j]<arr[j-increate]){
				swap(arr,j,j-increate);
				j-=increate;
			}
		}
	}
}
void print(int *arr,int n){
	for(int i=0;i<n;i++){
		printf("%d ",arr[i]);
	}
}
int main(int argc, char** argv) {
	int arr[]={4,56,23,98,45,5,6,87};
	shellSort(arr,8);
	print(arr,8);
	return 0;
}

注:所用图为dreamcatcher-cx大神的博客

6.堆排序

  • 核心思想:

    • 前提知识:堆其实就是一种特殊的完全二叉树,分为大顶堆和小顶堆,大顶堆就是指父节点>=左右孩子结点,而左右孩子结点之间的大小关系随意,小顶堆反之
    • 堆排序核心:就是先把序列构建成大顶堆序(升序用大顶堆),然后大顶堆的根节点和最后一个结点交换位置,这样一来每交换一次就得到当前序列的最大值,并把它放在了最后面,接着把剩下的序列继续构建成大顶堆,重复上面动作,直到序列只剩一个
    • 复杂度分析:
      • 最好情况:O(nlogn)
      • 最差情况:O(nlogn)
      • 平均:O(nlogn)
      • 辅助空间:O(1)

  • 稳定性:不稳定

##图解##

  • 注:大顶堆,小顶堆的左右孩子的大小随意

这里写图片描述

对应的在数组中的位置如下 这里写图片描述

  • 第一步,给定无序序列如下

这里写图片描述

  • 第二步,从最后一个非叶节点开始,从左至右,从上至下调整二叉树,形成大顶堆 (注:第一个非叶节点为length/2-1,这里为arr[1]=6)

    从arr[1]处开始构建堆

这里写图片描述

接着处理arr[0] 这里写图片描述 由于交换完后,arr[1]处又乱了,继续处理arr[1]

这里写图片描述 至此,大顶堆构建完成

  • 第三步,得到大顶堆后,让大顶堆首元素和末尾元素交换,如此让最大元素处于最末位置,由于交换会导致新二叉树不满足大顶堆性质,于是要进行调整,让它重新变成大顶堆,接着又是首元素和末尾元素交换,得到第二大的元素,并排放在倒数第二的位置,如此反复执行交换,调整,交换...

交换1 这里写图片描述 调整1 这里写图片描述 交换2 这里写图片描述

后续如下 这里写图片描述 代码如下

#include <iostream>

void swap(int *&arr,int i,int j){
	int temp=arr[i];
	arr[i]=arr[j];
	arr[j]=temp;
} 

void buildHeap(int *&arr,int i,int n){//以arr[i]为根建立堆(升序大顶堆) 
	int temp=arr[i]; 
	for(int k=2*i+1;k<n;k=2*k+1){
		if(k+1<n&&arr[k]<arr[k+1]) {
			k++;
		}
		if(temp<arr[k]){
			arr[i]=arr[k];
			i=k;
		}else{
			break;	
		}
	}
	arr[i]=temp;
}
void heapSort(int arr[],int n){
	int i,j;
	for(i=n/2-1;i>=0;i--){//建好了堆 
		buildHeap(arr,i,n);
	}
	for(j=n-1;j>=0;j--){
		swap(arr,j,0);
		buildHeap(arr,0,j);
	} 
}
int main(int argc, char** argv) {
	int arr[]={4,12,35,98,4,44,58,13,15};
	heapSort(arr,9);
	for(int i=0;i<9;i++){
		printf("%d ",arr[i]);
	}
	return 0;
}

注:所用图均来自dreamcatcher-cx大神的博客

7.归并排序

  • 核心思想: 是分治算法的典型应用,归并排序中的来说就两步

    • 分:把序列分成左右子序列,左右子序列又细分成各自的左右子序列,直到左右子序列都各只有一个(递归实现)
    • 治:对分好的子序列分别进行合并排序,这里排序的方法是定义两个哨兵,左哨兵指向左子序列的首元素,右哨兵指向右子序列的首元素,然后两者指向的值进行比较,谁小,则谁先存入新数组,直到左右序列都存完

  • 时间复杂度:

    • 最好最差均为O(nlogn)
    • 辅助空间为O(n)
    • 稳定性:稳定

##图解## 这里写图片描述

这里写图片描述

递归实现代码

#include <iostream>

void merge(int arr[],int left,int right,int mid,int temp[]){//合(并) 
	int k=0,t=0;
	int i=left;
	int j=mid+1;
	while(i<=mid&&j<=right){//若左右哨兵有一方越界,则此while雪崩 
		if(arr[i]<arr[j]){
			temp[k++]=arr[i++];
		}else{
			temp[k++]=arr[j++];
		}
	}
	while(i<=mid){//剩下左哨兵,则左边开门送连环抱 
		temp[k++]=arr[i++];
	}
	while(j<=right){//剩下右哨兵,则右边开门送连环抱 
		temp[k++]=arr[j++];
	}
	while(left<=right){//把排好序的临时数组复制到arr中 
		arr[left++]=temp[t++];
	}
}
void sort(int arr[],int left,int right,int temp[]){//分(归) 
	if(left<right){//当left==right时(即分到只有一个元素时,结束) 
		int mid=(left+right)/2;//把数组分成[left...mid]和[mid+1...right]两部分 
		sort(arr,left,mid,temp);//分左半部分 
		sort(arr,mid+1,right,temp);//分右半部分 
		merge(arr,left,right,mid,temp);//把分好的左右部分混合排好序 
	}
}

int main(int argc, char** argv) {
	int temp[100];
	int arr[]={9,8,7,6,4,2,5,3,2,1};
	sort(arr,0,9,temp);
	for(int i=0;i<10;i++){
		printf("%d ",arr[i]);
	}
	return 0;
}

注:所用图为dreamcatcher-cx大神的博客

评论区

  1. 目录
留言