必知必会的八大排序算法

基于Java的排序算法(介绍8种)

可视化动画演示:https://visualgo.net/zh

  • 交换排序:冒泡+快速
  • 插入排序:直接插入+希尔
  • 选择排序:简单选择+堆
  • 归并排序
  • 基数排序

在这里插入图片描述

一、冒泡排序:循环定尾数

void bubbletSort(int[] arr){
	for(int i=0;i<arr.length-1;i++){			//冒泡次数
		for(int j=0;j<arr.length-1-i;j++){		//数值对比
			if(arr[j] > arr[j+1]){
				swap();
			}
		}
	}
}

二、快速排序:选标准数-左小右大-递归

void quickSort(int[] arr,int start,int end){
	if(start>=end){
		return ;
	}
	//选数组的第0个数字作为标准数
	int stard = arr[start];
	//记录需要排序的下标
	int low = start;
	int high = end;
	
	while(low<high){
		while(low<high && stard <= arr[high]){
			high--;
		}
		arr[low] = arr[high];		//将元素arr[high]放入arr[low]中
		while(low<high && arr[low]<=stard){
			low++;
		}
		arr[high] = arr[low];		//将元素arr[low]放入arr[high]中
	}
	//把标准数赋给低所在位置的元素
	arr[low] = stard;
	//递归处理所有小的数字
	quickSort(arr,start,low);
	//递归处理所有小的数字
	quickSort(arr,low+1,end);
}

三、直接插入排序:循环定首位数

void insertSort(int[] arr){
	for(int i=1;i<arr.length;i++){		//遍历所有数值
		if(arr[i]<arr[i-1]){		//若当前数比前一个数小
			int temp = arr[i];	//把当前遍历数字存起来
			int j;
			for(j=i-1;j>=0 && temp<arr[j];j--){		//遍历当前数字前面的所有数字
				arr[j+1] = arr[j];			//把前一个数赋值给后一个数
			}
			arr[j+1] = temp;		//把临时变量赋给不满足条件的后一个元素
		}
	}
}

四、希尔排序:步长+直接插入排序

void shellSort(int[] arr){
	for(int d=arr.length/2;d>0;d/=2){			//遍历所有步长
		for(int i=d;i<arr.length;i++){				//遍历所有元素
			for(int j=i-d;j>=0;j-=d){					//遍历本组中所有的元素
				if(arr[j]>arr[j+d]){
					swap();
				}
			}
		}
	}
}

五、简单选择排序:循环遍历找min

void selectSort(int[] arr){
	for(int i=0;i<arr.length;i++){			//遍历所有的数
		int minIndex = i;
		for(int j=i+1;j<arr.length;j++){
			if(arr[minIndex] > arr[j]){
				minIndex = j;
			}
		}
		if(i != minIndex){			//下标不一致-互换
			int temp = arr[i];
			arr[i] = arr[minIndex];
			arr[minIndex] = temp;
		}
	}
}

六、堆排序:大顶堆+小顶堆

void heapSort(int[] arr) {
	for (int i = (arr.length - 1) / 2; i >= 0; i--) {	//创建堆
		adjustHeap(arr, i, arr.length);					//从第一个非叶子结点从下至上,从右至左调整结构
	}

	for (int i = arr.length - 1; i > 0; i--) {			//调整堆结构+交换堆顶元素与末尾元素
		//将堆顶元素与末尾元素进行交换
		int temp = arr[i];
		arr[i] = arr[0];
		arr[0] = temp;

		adjustHeap(arr, 0, i);				//重新对堆进行调整
	}
}

/**
 * 调整堆
 * @param arr 待排序列
 * @param parent 父节点
 * @param length 待排序列尾元素索引
 */
void adjustHeap(int[] arr, int parent, int length) {
	int temp = arr[parent];				//将temp作为父节点
	int lChild = 2 * parent + 1;		//左孩子

	while (lChild < length) {
		int rChild = lChild + 1;		//右孩子
		// 如果有右孩子结点,并且右孩子结点的值大于左孩子结点,则选取右孩子结点
		if (rChild < length && arr[lChild] < arr[rChild]) {
			lChild++;
		}

		// 如果父结点的值已经大于孩子结点的值,则直接结束
		if (temp >= arr[lChild]) {
			break;
		}

		// 把孩子结点的值赋给父结点
		arr[parent] = arr[lChild];

		//选取孩子结点的左孩子结点,继续向下筛选
		parent = lChild;
		lChild = 2 * lChild + 1;
	}
	arr[parent] = temp;
}

七、归并排序:先排序后归并

void mergeSort(int[] arr,int start,int end) {
	//中间下标
	int middle = (start+end)/2;	
	if(start < end) {
		//递归:左边数组排序
		mergeSort(arr,start,middle);
		//递归:右边数组排序
		mergeSort(arr,middle+1,end);
		//归并
		merge(arr, start,middle, end);
	}
}
void merge(int[] arr,int start, int middle,int end){		
	//存储归并后的临时数据
	int[] temp = new int[end-start+1];
	//第一个数组中需要遍历的下标
	int i = start;
	//第二个数组中需要遍历的下标
	int j = middle+1;
	//索引下标
	int index = 0;
	while(i<=middle && j<=end) {
		if(arr[i]<=arr[j]) {
			temp[index] = arr[i];
			i++;
		}else {
			temp[index] = arr[j];
			j++;
		}
		index++;
	}
	//若有剩余-直接插入
	while(i<=middle) {
		temp[index] = arr[i];
		i++;
		index++;
	}
	//若有剩余-直接插入
	while(j<=end) {
		temp[index] = arr[j];
		j++;
		index++;
	}
	//将临时数组赋值给原数组
	for(int k=0;k<temp.length;k++) {
		arr[k+start] = temp[k];
	}
}
归并排序-代码格式浓缩版
//归并排序-代码格式浓缩版
void merge(int[] arr, int start, int end) {
	if(start == end)	return ;
	int mid = start+(end-start)>>1;
	merge(arr,start,mid);
	merge(arr,mid+1,end);
	
	int[] temp = new int[end-start+1];
	int i = start, j = mid+1, k = 0;
	while(i <= mid && j <= end)
		temp[k++] = arr[i]<arr[j]?arr[i++]:arr[j++];
	while(i <= mid)
		temp[k++] = arr[i++];
	while(j < end)
		temp[k++] = arr[j+1];
	
	System.arraycopy(temp,0,arr,start,end);
}

八、基数排序:个位数-十位数-百位数-...-存数组-依次取出

void radixSort(int[] arr){
	//数组中最大的数
	int max = Integer.MIN_VALUE;
	for(int i=0;i<arr.length;i++){
		if(arr[i] > max){
			max = arr[i];
		}
	}
	//计算最大数是几位数
	int maxLength = (max+"").length;
	//用于临时存储数据的数组
	int[][] temp = new int[10][arr.length];
	//用于记录temp中相应数组存放的数字的数量
	int[] counts = new int[10];
	//根据最大长度的数决定比较的次数
	for(int i=0,n=1;i<maxLength;i++,n*=10){
		//计算每一个数的余数
		for(int j =0;j<arr.length;j++){
			//计算余数
			int ys = arr[j]/n%10;
			//把当前遍历的数据放入指定的数组中
			temp[ys][counts[ys]] = arr[j];
			//记录数量
			counts[ys]++;
		}
		//记录元素取的元素需要放的位置
		int index = 0;
		//把数字取出来
		for(int k=0;k<counts.length;k++){
			//记录数量的数组中当前余数记录的数量不为0
			if(counts[k] != 0){
				//循环取出元素
				for(int m=0;m<counts[k];m++){
					//取出元素
					arr[index] = temp[k][m];
					index++;
				}
				//把数量置空
				counts[k] = 0;
			}
		}
	}
}

改进:基于队列实现的基数排序

end
  • 作者:suoyue_zhan(联系作者)
  • 发表时间:2020-09-13 04:06:20
  • 版权声明:自由转载-非商用-非衍生-保持署名(创意共享3.0许可证)
  • 转载声明:如果是转载栈主转载的文章,请附上原文链接
  • 公众号转载:请在文末添加作者公众号二维码(公众号二维码见右边,欢迎关注)
  • 评论