冒泡排序、选择排序、插入排序、快速排序

搬运自：https://www.bilibili.com/video/BV15b4y117RJ?spm_id_from=333.999.0.0

冒泡排序文字描述（以升序为例）：
1.依次比较数组中相邻两个元素的大小，若a[j]>a[j+1]，则交换连个元素，两两都比较一遍称为一轮冒泡，结果是让最大的元素排至最后
2.重复以上步骤，直至整个数组有序

冒泡排序是一种稳定的排序算法

代码：

	public static int[] swap(int[] a,int i,int j){
		int temp=a[i];
		a[i]=a[j];
		a[j]=temp;
		return a;
	}
	//平均时间复杂度O^2
	public static int[] bubble(int[] a){
		for(int j=0;ja[i+1]){
					swap(a,i,i+1);
					swapped=true;
				}
			}
			if(!swapped){
				break;
			}
		}
		return a;
	}
	//平均时间复杂度O^2，在有序的情况下是O（只需要进行一轮冒泡）
	public static int[] bubble_v2(int[] a){
		while(true){
			int last=a.length-1;  //最后一次交换的索引
			for(int i=0;ia[i+1]){
					swap(a,i,i+1);
					last=i;
				}
			}
			if(last==0){
				break;
			}
		}
		return a;
	}

选择排序文字描述（以升序为例）：
1.将数组分为两个子集，排序的和未排序的，每一轮从未排序的子集中选出最小的元素，放入排序子集
2.重复以上步骤，直至整个数组有序

冒泡排序是一种不稳定的排序算法

	//在有序度高的情况下，冒泡优秀于选择
	//平均时间复杂度O^2 ,一般情况选择优于冒泡，因为冒泡排序交换次数多，
	public static int[] select(int[] a){
		for(int j=0;j 
三、插入排序 
插入排序文字描述（以升序为例）：
 1.将数组分位两个区域，排序区域和未排序区域，每一轮从未排序区域中取出第一个元素，插入到排序区域（需要保证顺序）
 2.重复以上步骤，直至整个数组有序
 
插入排序是一种稳定的排序算法
 
优化方式：
 1.待插入元素进行比较时，遇到比自己小的元素，就代表找到了插入位置，无需进行后续比较
 2.插入时可以直接移动元素位置，而不是交换元素
 
与选择排序比较：
 1.二者时间复杂度都是O(n^2)
 2.大部分情况下，插入略优于选择
 3.有序集合插入的时间复杂度为O(n)
 4.插入排序属于有序的排序算法，而选择属于不稳定排序
 
代码：
 
	public static int[] insert(int[] a){
		for(int i=1;i=0){
				if(t 
四、快速排序 
快速排序文字描述：
 1.每一轮排序选择一个基准点，进行分区
 （1）让小于基准点的元素的进入一个分区，大于基准点的元素的进入另一个分区
 （2）当分区完成时，基准点元素的位置就是其最终位置
 2.在子分区内重复以上过程，直至子分区元素个数小于等于1
 
单边循环-快速排序 
单边循环快速排序（lomuto洛穆托分区方案）
 1.选择最右边的元素作为基准点元素
 2.j 指针负责找到比基准点元素小的元素，一旦找到则与i进行交换
 3.i 指针维护小于基准点元素的边界，也是每次交换的目标索引
 4.最后基准点与i交换，i即为分区位置
 
代码：
 
	public static void quick(int[] a,int l,int h){
		if(l>=h){
			return;
		}
		int p = partition1(a,l,h);  // p:基准点的索引值
		quick(a,l,p-1);  //左边分区的范围确定
		quick(a,p+1,h);  //右边分区的范围确定
	}
     //单边循环——分区
	public static int partition1(int[] a,int l,int h){ //l,h分区的上下边界
		//返回值代表了基准点元素所在的正确索引，用它确定下一轮分区的上下边界
		int pv=a[h]; //基准点元素
		int i=l;
		for(int j=l;j 
双边循环-快速排序 
双边循环快速排序（并不完全等价于hoare霍尔分区方案）
 1.选择最左边的元素作为基准点元素
 2.j 指针负责从右向左找比基准点小的元素，i指针负责从左向右找比基准点大的元素，一旦找到二者交换，直至i, j相交
 3.最后记住那点与i(此时i与j相等）交换，i即为分区位置
 
	public static void quick(int[] a,int l,int h){
		if(l>=h){
			return;
		}
		int p = partition1(a,l,h);  // p:基准点的索引值
		quick(a,l,p-1);  //左边分区的范围确定
		quick(a,p+1,h);  //右边分区的范围确定
	}
		//双边循环——分区
	public static int partition2(int[] a,int l,int h){ //l,h分区的上下边界
		//返回值代表了基准点元素所在的正确索引，用它确定下一轮分区的上下边界
		int pv=a[l]; //基准点元素
		int i=l;
		int j=h;
		while(ipv){
				j--;
			}
			// i从左找比基准点元素大的元素
			while(i 
快速排序特点 
1.平均时间复杂度是O(nlog2n),最坏时间复杂度O(n^2)
 2.数据量较大时，优势非常明显
 3.属于不稳定排序
 
若数组中重复元素很多，则快排优势减小
					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: http://outofmemory.cn/zaji/5717565.html