【计理02组06号】十大经典排序算法【上篇】

冒泡排序

冒泡排序（Bubble Sort）是基于交换的排序，每次遍历需要排序的元素，依次比较相邻的两个元素的大小，如果前一个元素大于后一个元素则两者交换，保证最后一个数字一定是最大的（假设按照从小到大排序），即最后一个元素已经排好序，下一轮只需要保证前面 n-1 个元素的顺序即可。

之所以称为冒泡，是因为最大/最小的数，每一次都往后面冒，就像是水里面的气泡一样。

排序（假设从小到大）的步骤如下：

  1. 从头开始，比较相邻的两个数，如果第一个数比第二个数大，那么就交换它们位置。
  2. 从开始到最后一对比较完成，一轮结束后，最后一个元素的位置已经确定。
  3. 除了最后一个元素以外，前面的所有未排好序的元素重复前面两个步骤。
  4. 重复前面 1 ～ 3 步骤，直到所有元素都已经排好序。

例如，我们需要对数组 [98，90，34，56，21] 进行从小到大排序，每一次都需要将数组最大的移动到数组尾部。

交换具体逻辑如下图所示：

接下来两轮排序确定好了第二个和第三个的位置，其实这个数组已经完成排序了，一共 5 个数，冒泡 4 次即可。

紫色表示已经排好的元素，橙红色表示正在比较/交换的元素，可以看出前面两次排序之后，已经确定好了最大两个数的位置。

冒泡排序Java代码

查看代码 
public class BubbleSort {
	public static void bubbleSort(int[] nums) {
		int size=nums.length;
		for(int i=0;i<size-1;i++) {
			System.out.println("第"+(i+1)+"轮交换开始");
			for(int j=0;j<size-1-i;j++) {
				if(nums[j]>nums[j+1]) {
					int temp=nums[j+1];
					nums[j+1]=nums[j];
					nums[j]=temp;
				}
			printf(nums);
			}
		}
		
	}
	public static void printf(int[] nums) {
	    for (int num : nums) {
	        System.out.print(num + " ");
	    }
	    System.out.println("");
	}
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int[]nums = new int[]{98,90,34,56,21};
	    printf(nums);
	    bubbleSort(nums);
	    
	}

}

冒泡排序Java代码运行结果

选择排序

前面说的冒泡排序是每一轮比较确定最后一个元素，中间过程不断地交换。而选择排序就是每次选择剩下的元素中最小的那个元素，与当前索引位置的元素交换，直到所有的索引位置都选择完成。

排序的步骤如下：

  • 从第一个元素开始，遍历其后面的元素，找出其后面比它更小的且最小的元素，若有，则两者交换，保证第一个元素最小。
  • 对第二个元素一样，遍历其后面的元素，找出其后面比它更小的且最小的元素，若存在，则两者交换，保证第二个元素在未排序的数中（除了第一个元素）最小。
  • 依次类推，直到最后一个元素，那么数组就已经排好序了。

比如，现在我们需要对 [98，90，34，56，21] 进行排序，动态排序过程如下：

前面两轮选择排序已经分别将 21 和 34 选择出来，放到最前面的位置。

剩下的排序是确定 56 和 90 的位置，最后一个 98 自然就是最大的数，不需要再排序。

选择排序Java代码

查看代码 

public class SelectionSort {
	public static void printf(int[] nums) {
	    for (int num : nums) {
	        System.out.print(num + " ");
	    }
	    System.out.println("");
	}
	public static void selectionSort(int []nums) {
		int times=0;
		int size=nums.length;
		int minIndex,temp;
		for(int i=0;i<size-1;i++) {
			System.out.print("第" + (i + 1) + "轮选择开始：");
			minIndex=i;
			for(int j=i+1;j<size;j++) {
				times++;
				if(nums[j]<nums[minIndex]) {
					minIndex=j;
				}
			}
			System.out.println("交换 "+nums[i]+"和"+nums[minIndex]);
			temp=nums[i];
			nums[i]=nums[minIndex];
			nums[minIndex]=temp;
			printf(nums);
		}
		System.out.println("比较次数："+times);
	}
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		    int[]nums = new int[]{98,90,34,56,21};
		    printf(nums);
		    selectionSort(new int[]{98,90,34,56,21});
	}

}

选择排序Java代码运行结果

插入排序

选择排序是每次选择出最小的放到已经排好的数组后面，而插入排序是依次选择一个元素，插入到前面已经排好序的数组中间，确保它处于正确的位置，当然，这是需要已经排好的顺序数组不断移动。步骤描述如下：

  1. 从第一个元素开始，可以认为第一个元素已经排好顺序。
  2. 取出后面一个元素 n，在前面已经排好顺序的数组里从尾部往头部遍历，假设正在遍历的元素为 nums[i]，如果 num[i] > n，那么将 nums[i] 移动到后面一个位置，直到找到已经排序的元素小于或者等于新元素的位置，将 n 放到新腾空出来的位置上。如果没有找到，那么 nums[i] 就是最小的元素，放在第一个位置。
  3. 重复上面的步骤 2，直到所有元素都插入到正确的位置。

以数组 [98，90，34，56，21] 为例，动态排序过程如下：

具体的排序过程如下：

第一次假设第一个元素已经排好，第二个元素 90 往前面查找插入位置，正好查找到 98 的位置插入，第二轮是 34 选择插入位置，选择了第一个元素 90 的位置插入，其后面的元素后移。

第三轮排序则是 56 选择适合自己的位置插入，第四轮是最后一个元素 21 往前查找适合的位置插入：

插入排序Java代码

查看代码 

public class InsertionSort {
	public static void printf(int[] nums) {
	    for (int num : nums) {
	        System.out.print(num + " ");
	    }
	    System.out.println("");
	}
	
	public static void insertionSort(int[] nums) {
		if(nums==null) {
			return;
		}
		int size=nums.length;
		int index,temp;
		for(int i=1;i<size;i++) {
			// 当前选择插入的元素前面一个索引值
			index=i-1;
			// 当前需要插入的元素
			temp=nums[i];
			while(index>=0&&nums[index]>temp) {
				nums[index+1]=nums[index];
				index--;
			}
			// 插入空出来的位置
			nums[index+1]=temp;
			System.out.print("第" + (i) + "轮插入结果：");
			printf(nums);
		}
	}
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		    int[]nums = new int[]{98,90,34,56,21};
		    printf(nums);
		    insertionSort(nums);
	}

}

插入排序Java代码运行结果

希尔排序

希尔排序（Shell’s Sort）又称“缩小增量排序”（Diminishing Increment Sort），是插入排序的一种更高效的改进版本，同时该算法是首次冲破 O(n^2) 的算法之一。

插入排序的痛点在于不管是否是大部分有序，都会对元素进行比较，如果最小数在数组末尾，想要把它移动到数组的头部是比较费劲的。希尔排序是在数组中采用跳跃式分组，按照某个增量 gap 进行分组，分为若干组，每一组分别进行插入排序。再逐步将增量 gap 缩小，再每一组进行插入排序，循环这个过程，直到增量为 1。

希尔排序基本步骤如下：

  1. 选择一个增量 gap，一般开始是数组的一半，将数组元素按照间隔为 gap 分为若干个小组。
  2. 对每一个小组进行插入排序。
  3. 将 gap 缩小为一半，重新分组，重复步骤 2（直到 gap 为 1 的时候基本有序，稍微调整一下即可）。

以数组 [98，90，34，56，21，11，43，61] 为例子

同样以数组 [98，90，34，56，21，11，43，61] 为例子，元素个数为 8，首次 gap 为 4，元素分为 4 组，同颜色视为一组，对相同颜色进行插入排序，这样保证了大致位置上大的元素在后面，小的元素在前面。

第二轮希尔排序，gap = 4/2 = 2，则元素可以分为两组，同颜色视为一组，仍是对同组的进行插入排序：

最后一轮，gap= 2/2 =1，则所有元素视为一组，相当于对所有元素进行插入排序，这时候元素已经基本有序，只需要做小范围的调整即可。

希尔排序是非稳定排序算法，每一组的排序，都确保了这一组的数据基本有序，整体上也是基本有序。

希尔排序Java代码

查看代码 

public class ShellSort {
	public static void printf(int[] nums) {
	    for (int num : nums) {
	        System.out.print(num + " ");
	    }
	    System.out.println("");
	}
	public static void shellSort(int[] nums) {
		int times=1;
		for(int gap=nums.length/2;gap>0;gap/=2) {
			System.out.print("第" + (times++) + "轮希尔排序, gap= " + gap + " ,结果：");
		
		for(int i = gap;i<nums.length;i++) {
			int j=i;
			int temp=nums[j];
			if(nums[j]<nums[j-gap]) {
				while(j-gap>=0&&temp<nums[j-gap]) {
					nums[j]=nums[j-gap];
					j-=gap;
				}
				nums[j]=temp;
			}
		}
		printf(nums);
		}
	}
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		 int[] nums = new int[]{98, 90, 34, 56, 21, 11, 43, 61};
		 printf(nums);
		 shellSort(nums);
	}

}

希尔排序Java代码运行结果

快速排序

快速排序比较有趣，选择数组的一个数作为基准数，一趟排序，将数组分割成为两部分，一部分均小于/等于基准数，另外一部分大于/等于基准数。然后分别对基准数的左右两部分继续排序，直到数组有序。这体现了分而治之的思想，其中还应用到挖坑填数的策略。

算法的步骤如下：

  1. 从数组中挑一个元素作为基准数，一般情况下我们选择第一个 nums[i]，保存为 standardNum，可以理解为 nums[i] 坑位的数被拎出来了，留下空的坑位。
  2. 取数组的左边界索引指针 i，右边界索引指针 j，j 从右边往左边，寻找到比 standardNum 小的数，停下来，写到 nums[i] 的坑位，nums[j] 的坑位空出来。 索引指针i 从左边往右边找，寻找比 standardNum 大的数，停下来，写到 nums[j] 的坑位，这个时候，num[i] 的坑位空出来（前提是 i 和 j 不相撞）。
  3. 上面的 i 和 j 循环步骤 2，直到两个索引指针 i 和 j 相撞，将基准值 standardNum 写到坑位 nums[i] 中，这时候，standardNum 左边的数都小于等于它本身，右边的数都大于等于它本身。
  4. 分别对 standardNum 左边的子数组和右边的子数组，循环执行前面的 1，2，3，直到不可再分，并且有序。

以数组 [61，90，34，56，21，11，43，68] 为例，动态排序过程如下：

快速排序Java代码

查看代码 
public class QuickSort {
	public static void printf(int[] nums) {
	    for (int num : nums) {
	        System.out.print(num + " ");
	    }
	    System.out.println("");
	}
	public static void quickSort(int[] nums) {
		quickSort(nums,0,nums.length-1);
	}
	public static void quickSort(int nums[],int left,int right) {
		System.out.println("[left,right]:["+left+","+right+"]");
		if(left<right) {
			int i=left,j=right,standardNum=nums[left];
			while(i<j) {
				while(i<j&&nums[j]>=standardNum) {
					j--;
				
			}
			System.out.print("standardNum:"+standardNum+",第1个小于等于standardNum的数："+nums[i]);
			if(i<j) {
				nums[i]=nums[j];
				i++;
			}
			while(i<j&&nums[i]<standardNum) {
				i++;
			}
			System.out.println(",第1个大于等于standardNum的数："+nums[i]);
			if(i<j) {
				nums[j]=nums[i];
				j--;
			}
		}
		
		nums[i]=standardNum;
		printf(nums);
		quickSort(nums,left,i-1);
		printf(nums);
		quickSort(nums,i+1,right);
	}
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int[] nums = new int[]{61, 90, 34, 56, 21, 11, 43, 68};
	    printf(nums);
	    quickSort(nums);
	}

}

快速排序Java代码运行结果

实验总结

前面学习了五种排序算法，它们的复杂度以及特点在这里总结一下：

  • 冒泡排序：基本最慢，时间复杂度最好为 O(n)，最坏为 O(n2)，平均时间复杂度为 O(n2)，空间复杂度为 O(1)，稳定排序算法。
  • 选择排序：时间复杂度很稳定，最好最坏或者平均都是 O(n2)，空间复杂度为 O(1)，可以做到稳定排序。
  • 插入排序：时间复杂度最好为 O(n)，最坏为 O(n2)，平均时间复杂度为 O(n2)，空间复杂度为 O(1)，稳定排序算法。
  • 希尔排序：希尔增量下最坏的情况时间复杂度是 O(n2)，最好的时间复杂度是 O(n) （也就是数组已经有序），平均时间复杂度是 O(n3/2)，属于不稳定排序。
  • 快速排序：时间复杂度最差的情况是 O(n2)，平均时间复杂度为 O(nlogn)，空间复杂度，虽然快排本身没有申请额外的空间，但是递归需要使用栈空间，递归数的深度是 log2n，空间复杂度也就是 O( log2n)，属于不稳定排序。

每一种排序，都有其优缺点，我们应该根据场景选择合适的排序算法。

关于时间复杂度，我们一般使用大 O 表示法，它是一种体现算法时间复杂度的计法，通俗来讲，就是随着问题规模的增长，算法执行的指令数也在增长，时间复杂度越高，则执行时间增长越快。常见的算法时间复杂度由好到坏依次为： Ο(1) ＜ Ο(log2n) ＜ Ο(n) ＜ Ο(nlog2n) ＜ Ο(n^2) ＜ Ο(n^3) ＜ … ＜ Ο(2^n) ＜ Ο(n!) ，一个优秀的算法，自然少不了对低时间复杂度的追求。

但是我们也不能自然也不能忽略空间复杂度，也就是随着问题规模的增长，计算过程中所需要的存储空间增长的速度（增长率），其计算方式与时间复杂度类似。时间复杂度和空间复杂度是息息相关的两个概念，随着计算机空间越拉越大，不少的算法倾向于以空间换时间，这也是取舍的策略。

Tags:

VirMach 便宜 VPS

QNews

QNews