排序算法-冒泡、选择、堆、插入、归并、快速、希尔

  • 排序算法,默认是升序,左边的值是属于“小”值

理解比较大小后的交换:当前元素cur 和 左边的元素cur-1, 左边的比较大,就交换或者挪动 array[cur] = array[cur-1];

  • 编码的区间设置:建议是左闭 右开,方便 [begin, end)
  • 计算方面:使用右移 代替 除法

☺ 排序算法---重点放到比较的排序算法---冒泡、选择、堆排序 插入、归并、快速、希尔,

对于计数排序、基数排序不是面试的重点

排序算法-冒泡、选择、堆排序

一、冒泡排序:

为什么要叫冒泡排序? 因为形象生动上,每一轮都是最大的那个数冒到结尾

定义:

从头开始index=1 比较每一对相邻元素,如果第1个比第2个大,就交换它们的位置;执行完一轮后,最末尾那个元素就是最大的元素。

② 忽略 ① 中曾经找到的最大元素,重复执行步骤 ①,直到全部元素有序。

一轮的比较范围是从1 到 end,然后根据理解得到end 从最后一个元素开始不断减少】

  • 第一轮的比较,下标从1开始,左边比右边大进行交换

排序算法-冒泡、选择、堆、插入、归并、快速、希尔插图

		int array[] = {1, 3, 5, -1, -8};
		//比较 end 的结束范围,从最后一个元素-第二个元素
		for(int end = array.length - 1; end > 0; end--) {
			//冒泡排序-一轮的交换
			for(int begin = 1; begin 

优化1-冒泡排序

▪ 提前有序,终止比较(不一定有用:因为一般在随机数据中要提前有序的概率是很低的,)

  • 布尔变量:假设本轮已经有序
		//比较 end 的结束范围,从最后一个元素-第二个元素
		for(int end = array.length - 1; end > 0; end--) {
			boolean sorted = true;//假设提前有序
			//冒泡排序-一轮的交换
			for(int begin = 1; begin 

优化2-冒泡排序

  • 如果序列尾部已经局部是有序的,可以记录最后一次交换的位置,从而减少比较的次数。

排序算法-冒泡、选择、堆、插入、归并、快速、希尔插图1

int array[] = {1, 3, 5, -1, -8};
		//比较 end 的结束范围,从最后一个元素-第二个元素
		for(int end = array.length - 1; end > 0; end--) {
			int sortedIndex = 1;//记录最后一次交换的位置,初始值为1,是为了考虑一开始数组就是完全有序的
			//冒泡排序-一轮的交换
			for(int begin = 1; begin 

二、选择排序

为什么要叫选择排序? 因为每一轮都是把最大的那个数的位置给选择出来

定义:

从序列中找出最大的那个元素,然后与最末尾的元素交换位置;执行完一轮后,最末尾的那个元素就是最大的元素。

② 忽略 ① 中曾经找到的最大元素,重复执行步骤 ①

▪ 选择排序本质上看是冒泡的优化:

因为冒泡是从头到尾:相邻两个元素比较完就交换

选择排序是从头到尾:先找到最大元素位置,然后记录位置,最后才交换

		int array[] = {1, 3, 5, -1, -8};
		//比较 end 的结束范围,从最后一个元素-第二个元素
		for(int end = array.length - 1; end > 0; end--) {
			int maxIndex = 0;
			//选择排序-找出本轮的最大值
			for(int begin = 1; begin  10   8   10()	
                    maxIndex = begin;
				}
			}
			//交换,把本轮找到的最大一个数放到结尾
			int temp = array[maxIndex];
			array[maxIndex] = array[end];
			array[end] = temp;
		}

三、堆排序

▪ 堆排序本质上看是冒泡的优化:

选择排序是从头到尾:每一轮都在 从头到尾找到最大元素位置(内循环在找最大值)

---- 找最值,可以交给堆负责(优化)

▪ 堆排序:先原地建堆,然后尾部元素放到堆顶,然后下滤

int array[] = {1, 3, 5, -1, -8};
// 原地建堆
heapSize = arrayay.length;
for (int i = (heapSize >> 1) - 1; i >= 0; i--) {
		siftDown(i);
}
		
while (heapSize > 1) {
	// 交换堆顶元素和尾部元素
	int temp = array[0];
	array[0] = array[heapSize];
	array[heapSize] = temp;
	heapSize--;
    // 对0位置进行siftDown(恢复堆的性质)
	siftDown(0);
}


    /**
	 * 下滤
	*/
	private void siftDown(int index) {	
		int half = heapSize >> 1;
		Integer element = array[index];
		while(index  0) {
				childElement = array[childIndex = rightIndex];
			}
			
			if(compare(element, childElement) >= 0) break;
			//子结点大的话
			array[index] = childElement;
			index = childIndex;
		}
		array[index] = element;
	}

排序算法-插入排序

一、插入排序

插入排序非常类似于扑克牌的排序

定义:① 在执行过程中,插入排序会将序列分为2部分;头部是已经排好序的,尾部是待排序的

​ ② 从头开始扫描每一个元素;每当扫描到一个元素,就将它插入到头部合适的位置,使得头部数据依然保持有序

排序算法-冒泡、选择、堆、插入、归并、快速、希尔插图2

	private void sort(Integer[] array) {
------------------------------------------- 核心代码开始 ------------------------------------------------------------		
		for(int begin = 1; begin  0 && cmp(array[cur], array[cur - 1]) 

优化1-插入排序

  • 优化:挪动替换交换

排序算法-冒泡、选择、堆、插入、归并、快速、希尔插图3

	private void sort(Integer[] array) {
		for(int begin = 1; begin  0 && cmp(v, array[cur - 1]) 

优化2-插入排序

  • 找位置--使用二分搜索法(通过挪动左右指针,不断缩小一半的可能范围)

  • 使用二分搜索优化了比较次数

    细节:二分搜素的开始-结束区间[begin, end)

    • int begin = 0; int end = array.length;

    • 为什么结束要取 end,因为方便后续其他计算,比如算出该区间有多少元素

  • 优化二分搜素[原:查找位置]为[查找待插入的位置]

    ▪ 原:查找到位置

查找目标位置的:查找过程分成三种判断条件:小于,去左边查找;大于,去右边查找;等于直接返回目标

排序算法-冒泡、选择、堆、插入、归并、快速、希尔插图4

​ ▪ 现:查找到待插入位置

查找待插入的目标位置的:查找过程分成两种种判断条件:小于,去左边查找;大等于,去右边查找;因为这个等于不是待插入的目标位置

  • 待插入的目标位置是第一个大于 待插入原始的值v 的元素位置


排序算法-冒泡、选择、堆、插入、归并、快速、希尔插图5

	/**
	 * 查找待插入位置的索引
	 */
	private int search(int index) {//index 是待插入索引
		int begin = 0;
		int end = index;
		while(begin > 2;
			if(cmp(array[index], array[mid])  insertIndex; i--) {//挪动腾出空间
				array[i] = array[i - 1];
			}
			array[insertIndex] = v;
		}
	}

排序算法-归并排序

一、归并排序

定义:

① 不断地将当前序列平均分割成2个子序列;直到不能再分割(序列中只剩1个元素)

② 不断地将2个子序列合并成一个有序序列;直到最终只剩下1个有序序列

排序算法-冒泡、选择、堆、插入、归并、快速、希尔插图6

	int[] leftArray;
	int[] array;

	private void sort(int begin, int end) {
		if(end - begin > 1;
		sort(begin, mid);//左边归并
		sort(mid, end);//右边归并
		merge(begin, mid, end);//最后进行合并
	}
	

	/**
	 * 将 [begin, mid) 和 [mid, end) 范围的序列数组合并成一个有序序列 
	 */
	private void merge(int begin, int mid, int end) {
		int li = 0, le = mid - begin;//左边数组leftArray
		int ri = mid, re = end;//右边数组
		int ai = begin;//arrayay 的索引
		for(int i = li; i 

排序算法-快速排序、希尔排序

一、快速排序

快速排序的本质:逐渐将每一个元素都转换成轴点元素

定义:

① 从序列中选择一个轴点元素(pivot)

▪ 假设每次选择 0 位置的元素为轴点元素

② 利用 pivot 将序列分割成 2 个子序列

▪ 将小于 pivot 的元素放在pivot前面(左侧)

▪ 将大于 pivot 的元素放在pivot后面(右侧)

▪ 等于pivot的元素放哪边都可以

③ 对子序列进行 ① ② 操作

▪ 直到不能再分割(子序列中只剩下1个元素)

是一个递归排序:从轴点切分成两部分,不断地对左部分进行快速排序,不断地对右部分进行快速排序

排序算法-冒泡、选择、堆、插入、归并、快速、希尔插图7

判断该元素是 "甩"到左边 还是 右边,不加等号,因为加上等号会使得轴点元素分割出来的子序列极度不均匀

  • 比如 6 6 6 6 6,轴点是6,那么取等号,全部给甩到一边了

	int[] array;

	private void sort(int begin, int end) {
		if(end - begin 轴点元素,不是目标,要在右边找“小”
					end--;
				}else {
					array[begin++] = array[end];
					break;
				}
			}
			
			while(begin  0) {// 左边元素

二、希尔排序

切分成n 列然后进行排序--> 逆序对数量逐渐减少 --> 希尔排序,底层是使用插入排序,也可以把希尔看成是对插入排序的改进版

排序算法-冒泡、选择、堆、插入、归并、快速、希尔插图8

	int[] array;

	private void sort() {
		List stepSequence = shellStepSequence();
		for(Integer step: stepSequence) {//按照每个步长进行切割,然后进行一一对应的比较 排序
			sort(step);
		}
	}
	
	/**
	 * 按照给定的步长进行切割,然后对 step 列进行排序
	 */
	private void sort(Integer step) {
 ------------------------------------------- 核心代码开始 ------------------------------------------------------------	     
		// col: 第几列
		for(int col = 0; col  col && cmp(array[cur], array[cur - step])  shellStepSequence(){
		List stepSequence = new ArrayList();
		int step = array.length;
		while((step >>= 1) > 0) {
			stepSequence.add(step);
		}
		return stepSequence;
	}
	
	

	protected int cmp(int v1, int v2) {
		return v1 - v2;
	}
	
	protected void swap(int v1, int v2) {
		int tmp = v1;
		v1 = v2;
		v2 = tmp;
	}

▪ 冒泡、选择、插入、归并、快速、希尔、堆排序,都是基于比较的排序 [面试会考]

  • 平均时间复杂度目前最低是 O(nlogn)

▪ 计数排序、桶排序、基数排序,都不是基于比较的排序 [面试不考,作为了解]

  • 它们是典型的用空间换时间,在某些时候,平均时间复杂度可以比 O(nlogn) 更低

排序算法-计数排序、基数排序、桶排序

一、计数排序

排序算法-冒泡、选择、堆、插入、归并、快速、希尔插图9

细节:在java 整型数组,new出数组之后,内部元素默认都是 0

int counts = new int[10]; //new 完,默认所有元素都是0

	int[] array;

	private void sort() {
		//找出最大值
		int max = array[0];
		for(int i = 1; i  max) {
				max = array[i];
			}
		}
 ------------------------------------------- 核心代码开始 ------------------------------------------------------------	     
		// 开辟内存空间,存储每一个整数出现的次数
		int[] counts = new int[1 + max];//整型数组,new出数组之后,内部元素默认都是 0 
		
		//统计每个整数出现的次数
		for(int i = 0; i  0) {
				array[index++] = i;
			}
		}
------------------------------------------- 核心代码结束 ------------------------------------------------------------	         
	}	

■ 计数排序缺点:

  • 无法对负整数进行排序

  • 极其浪费内存空间

  • 是个不稳定的排序

■ 计数排序的优化

排序算法-冒泡、选择、堆、插入、归并、快速、希尔插图10

	int[] array;

	private void sort() {
		// 找出最大值、最小值
		int max = array[0];//最大值
		int min = array[0];//最小值
		for(int i = 1; i  max) {
				max = array[i];
			}
			if(array[i] = 0; i--) {
			newArray[--counts[array[i] - min]] = array[i];// 公式 count[k - min] -p 其中p是该元素k倒数着出现的次数
		}
------------------------------------------- 核心代码结束 ------------------------------------------------------------	  		
		//将有序数组赋值到array
		for(int i = 0; i 

二、基数排序

定义:依次对个位数、十位数、百位数、千位数、万位数...进行排序(从低位到高位)

排序算法-冒泡、选择、堆、插入、归并、快速、希尔插图11

	int[] array;

	private void sort() {
		// 找出最大值
		int max = array[0];
		for (int i = 1; i  max) {
				max = array[i];
			}
		}
		// max = 593
		// 个位数 array[i] / 1 % 10 = 3
		// 十位数 array[i] / 10 % 10 = 9
		// 百位数 array[i] / 100 % 10 = 5
		for (int divider = 1; divider = 0; i--) {
//			newArray[--counts[array[i]的基数] = array[i];
			newArray[--counts[array[i] / divider % 10]] = array[i];
		}

		// 将有序数组赋值到array
		for (int i = 0; i 

■ 基数排序的另外一种思路:元素先存到桶里,然后再回收

排序算法-冒泡、选择、堆、插入、归并、快速、希尔插图12

三、桶排序

如果本文对你有帮助的话记得给一乐点个赞哦,感谢!

文章来源于互联网:排序算法-冒泡、选择、堆、插入、归并、快速、希尔

THE END
分享
二维码