java代码实现排序算法详解 _排序算法

排序算法大致分为内部排序和外部排序两种
内部排序：待排序的记录全部放到内存中进行排序，时间复杂度也就等于比较的次数
外部排序：数据量很大，内存无法容纳，需要对外存进行访问再排序，把若干段数据一次读入内存使用内部排序的方法进行排序后写入外存，再将这若干个已经排序的数据进行归并，时间复杂度等于IO(访问外存)的次数

文章插图

1、冒泡算法交换排序。属于比较简单直观的排序算法，以升序为例（从小到大），每次比较相邻的两个元素，如果左侧元素比右侧的大，则交换两个元素的位置，每次把循环中最大的元素放在循环的最后，像冒泡一样从小到最大。
1.1 算法步骤

比较 a[j] 和 a[j+1]，如果 a[j] > a[j+1]，swap交换两个元素在数组中的位置
让每一对相邻元素进行以上的比较，直到把最大的值放到比较的数组最后
重复以上步骤n-1次

1.2 时间复杂度? 总共需要比较次数(n为数组元素个数 n >= 1)：
[O(n)=(n-1)+(n-2)+cdots+1=frac{(n-1)*n}{2}\ 取最高次幂O(n)=n^2 ]

1.3 代码实现

public int[] bubbleSort(int[] arr) { // 外层循环，数组长度为 n，循环次数为 n-1 for (int i = 0; i < arr.length - 1; i++) {// 内层循环，循环次数为 n-1-i，找到一个最大值放在，arr[n-1-i]的位置for (int j = 0; j < arr.length - 1 - i; j++) {// 比较相邻的两个值，把相对大的值放在数组下标大的地方if (arr[j] > arr[j + 1]) {// swap交换int temp = arr[j];arr[j] = arr[j + 1];arr[j + 1] = temp;}} } return arr;}

1.4 图示? 如图，即使第二次循环已经排好序，但是程序不晓得，仍会继续循环进行排序，最后一次，只有两个元素进行排序比较，直接排序完成，排序次数 n-1 。

文章插图

文章插图

2、快速排序? 交换排序。选择一个基准值，将数组划分两个区域，左侧的值全部比右侧的值小，然后分别对两个区域继续进行区域的划分与排序，直到排序完成。
2.1 算法步骤

从数组中按照一定的规则选择一个元素作为基准值
把基准值与其他元素进行比较，将元素分成两部分，把所有比基准值小的值放在左侧，所有比基准值大的放在右侧。即进行区域划分
通过递归上述操作，再次将左右两区域进行区域划分，完成排序

2.2 时间复杂度? 对区域划分取特殊值，假设n为2的幂，每次都将n个数平均划分，所以第一次对一整个区域进行循环n次划分2个区域，第二次对两个区域分别进行循环(frac{n}{2})次，共n次，划分4个区域，第三次对4个区域分别进行循环(frac{n}{4})次，共计n次，以此类推，最后一次为第log2n次，划分的每个区域仅有一个元素。即：
[O(n)=n*log_2n ]

2.3 代码实现

private static int[] quickSort(int[] arr, int left, int right) { if (left < right) {int partitionIndex = partition(arr, left, right);// 左侧右侧区间再分别进行排序quickSort(arr, left, partitionIndex - 1);quickSort(arr, partitionIndex + 1, right); } return arr;}// 以基准值将数组arr的left~right区间进行分区，保证返回的下标左侧元素比基准值小，右侧比基准值大private static int partition(int[] arr, int left, int right) { // 设定基准值为最左侧元素，本身不参与循环中的交换，仅在最后放到index的位置 int pivot = left; // 该index用于标记一个下标，代表当前已经遍历的元素中，index位置的元素是最后一个比基准值小的元素 // arr[index]本身以及数组左侧元素都小于基准值 int index = left; // 遍历left+1~right区间（因为基准值自身不需要进行比较交换） for (int i = left+1; i <= right; i++) {if (arr[i] < arr[pivot]) {// 保证从当前遍历到的最后一个比基准值小的元素的下一个元素开始交换，所以先++再交换index++;swap(arr, i, index);} } // 此时index为分界点，arr[index]<arr[index+1] // 其他元素交换完毕之后arr[index]的值应该为基准值，所以进行元素位置交换 swap(arr, pivot, index); // 此时arr[index]两侧元素左小右大 return index;}// 元素交换private static void swap(int[] arr, int i, int j) { int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp;}

2.4 图示