常用排序算法的Java实现与分析
由于需要分析算法的最好时间复杂度和最坏时间复杂度,因此这篇文章中写的排序都是从小到大的升序排序。
带排序的数组为arr,arr的长度为N。时间复杂度使用TC表示,额外空间复杂度使用SC表示。
好多代码都用到了交换arr[i]和arr[j]的地方,这里先给出代码。
private static void swap(int[] arr, int i, int j) { int tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp; }
(1)插入排序
1.1直接插入排序
算法思想:初始时第一个元素是有序的,在插入元素arr[i]时,arr[0] ~arr[i – 1]已经是有序的了,将arr[i]插入其中即可。
稳定性:如果遇到和arr[i]相等的元素,那么将arr[i]放在后面,所以直接插入排序是稳定的。
复杂度分析:arr基本有序(升序)时,直接插入排序的TC是O(N);arr降序时,TC是O(N*N);平均时间复杂度O(N*N)。直接插入排序的SC是O(1)。
算法实现:
public class InsertionSort_StraightInsertionSort { public static int[] sis(int[] arr) { for (int i = 1; i < arr.length; i++) { for (int j = i - 1; j >= 0 && arr[j] > arr[j + 1]; j--) { swap(arr, j, j + 1); } } return arr; }
}
1.2希尔排序
算法思想:希尔排序的实质就是分组插入排序,该方法又称为缩小增量排序。先将arr分割成若干个子序列(由相隔某个增量的元素组成),分别进行直接插入排序,然后依次缩小增量再进行排序。待整个序列中的元素基本有序(增量足够小时),再对全体元素进行一次直接插入排序。
稳定性:不稳定
复杂度分析:TC最好为O(N) ,最坏 O(N * N),平均TC为O(N*1.3)。SC为O(1)。
算法实现:
public class InsertionSort_ShellSort { public static int[] shellSort(int[] arr) { for (int gap = arr.length / 2; gap > 0; gap /= 2) { for (int i = gap; i < arr.length; i++) { for (int j = i - gap; j >= 0 && arr[j] > arr[j + gap]; j -= gap) { swap(arr, j, j + gap); } } } return arr; } }
(2)交换排序
2.1冒泡排序
算法思想:一次比较两个元素,如果他们的顺序错误就把他们交换过来。
稳定性:稳定
复杂度分析:arr升序时TC最好为O(N) ,arr降序时TC最坏 O(N * N),平均TC为O(N*N)。SC为O(1)
算法实现:
public class Exchange_Bubble { public static int[] bubbleSort(int[] arr) { for (int i = arr.length; i != 0; i--) { for (int j = 1; j < i; j++) { if (arr[j] < arr[j - 1]) { swap(arr, j - 1, j); } } } return arr; } }
2.2快速排序
算法思想:1.先从数列中取出一个数作为基准数;2.分区过程,将比这个数大的数全放到它的右边,小于或等于它的数全放到它的左边。3.再对左右区间重复第二步,直到各区间只有一个数。
稳定性:不稳定
复杂度分析:arr升序时TC最好为O(NLogN) ,arr降序时TC最坏 O(NLogN),平均TC为O(NLogN)。SC为O(1)
算法实现:
public class Exchange_QuickSort { public static int[] quickSort1(int[] arr) { return qs1(arr, 0, arr.length - 1); } private static int[] qs1(int[] arr, int left, int right) { if (left > right) { return arr; } int i = left; int j = right; int tmp = arr[left]; while (i < j) { while (i < j && arr[j] >= tmp) { j--; } while (i < j && arr[i] <= tmp) { i++; } if (i < j) { swap(arr, i, j); } } arr[left] = arr[i]; arr[i] = tmp; qs1(arr, left, i - 1); qs1(arr, i + 1, right); return arr; } }
(3)选择排序
3.1简单选择排序
算法思想:在要排序的一组数中,选择出最小的数与第一个数交换;然后在剩下的数中,选择出最小的数与第二个数交换,以此类推。
稳定性:稳定
复杂度分析:arr升序时,只是避免了交换元素的操作,TC最好仍旧为O(N*N) ;arr降序时TC最坏 O(N*N),平均TC为O(N*N)。SC为O(1)
算法实现:
public class SelectionSort_SimpleSelectionSort { public static int[] simpleSelectionSort(int[] arr) { for (int i = 0; i < arr.length; i++) { int minIdx = i; for (int j = i + 1; j < arr.length; j++) { if (arr[j] < arr[minIdx]) { minIdx = j; } } if (arr[minIdx] < arr[i]) { swap(arr, minIdx, i); } } return arr; } }
3.2堆排序
算法思想:从小到大排序,构建大顶堆(堆首先是一棵完全二叉树,大顶堆每个节点的值都不大于父节点的值),然后每次将堆顶元素和没有排序的最后的元素交换,重新构建堆(即重新得到最大的堆顶元素)。
稳定性:不稳定
复杂度分析:
最好情况:如果待排序数组是降序的,仍然需要O(N * logN)复杂度的比较操作,少了移动的操作;
最坏情况:如果待排序数组是升序的,不仅需要O(N * logN)复杂度的比较操作,而且需要O(N * logN)复杂度的交换操作。总的时间复杂度还是O(N * logN)。
在最好和最坏情况下,堆排序的时间复杂度都是O(NlogN)。堆排序时,由于每次重新恢复堆的时间复杂度为O(logN),共N – 1次堆调整操作,再加上前面建立堆时N / 2次向下调整,
每次调整时间复杂度也为O(logN)。两次次操作时间相加还是O(N * logN)。故堆排序的时间复杂度为O(N * logN)。
堆排序一般优于快速排序的重要一点是,数据的初始分布情况对堆排序的效率没有大的影响。
算法实现:
public class SelectionSort_HeapSort { public static int[] heapSort(int[] arr) { buildHeap(arr); for (int i = arr.length - 1; i >= 0; i--) { swap(arr, 0, i);//交换完后,大的元素跑到了数组的后面的部分 所以堆排序时 数组后面到前面逐渐变得有序 heapify(arr, 0, i); //调整回大顶堆,即重新找到未排序部分的最大值 } return arr; } private static void buildHeap(int[] arr) { for (int i = (arr.length - 1) / 2; i >= 0; i--) { heapify(arr, i, arr.length); } } //从index开始往下不断调整大顶堆 private static void heapify(int[] arr, int index, int heapSize) { int left = index * 2 + 1; int right = index * 2 + 2; int largest = index; while (left < heapSize) { if (arr[left] > arr[index]) { largest = left; } if (right < heapSize && arr[right] > arr[largest]) { largest = right; } if (largest != index) { swap(arr, largest, index); } else { break; } index = largest; left = index * 2 + 1; right = index * 2 + 2; } } }
(4)不基于比较的排序
4.1桶排序
算法思想:桶排序可用于最大最小值相差较大的数据情况,要求数据的分布必须均匀,否则可能导致数据都集中到一个桶中。
把数组 arr 划分为n个大小相同子区间(桶),每个子区间各自排序,最后合并。计数排序是桶排序的一种特殊情况,可以把计数排序当成每个桶里只有一个元素的情况。
1.找出待排序数组中的最大值max、最小值min;2.我们使用 动态数组ArrayList 作为桶,桶里放的元素也用 ArrayList 存储。桶的数量为(max-min)/arr.length+1
3.遍历数组 arr,计算每个元素 arr[i] 放的桶;4.每个桶各自排序;5.遍历桶数组,把排序好的元素放进输出数组
稳定性:稳定
复杂度分析:
N个待排数据,M个桶,平均每个桶[N/M]个数据的桶排序平均时间复杂度为:O(N)+O(M*(N/M)log(N/M))=O(N+N(logN-logM))=O(N+N*logN-N*logM)
当N=M时,即极限情况下每个桶只有一个数据时。桶排序的最好效率能够达到O(N)。
桶排序的平均时间复杂度为线性的O(N+C),其中C=N*(logN-logM)。如果相对于同样的N,桶数量M越大,其效率越高,最好的时间复杂度达到O(N)。
桶排序的空间复杂度 为O(N+M),如果输入数据非常庞大,而桶的数量也非常多,则空间代价无疑是昂贵的。
算法实现:
public class NoCompare_BucketSort { public static int[] bucketSort(int[] arr) { int max = Integer.MIN_VALUE; int min = Integer.MAX_VALUE; for (int cur : arr) { max = Math.max(max, cur); min = Math.min(min, cur); } //计算桶的数量并构建初始的桶 int bucketNum = (max - min) / arr.length + 1; // int bucketNum = (max - min) + 1; //每个桶中只有一个元素的时候就是计数排序 List<List<Integer>> buckets = new ArrayList<>(); for (int i = 0; i < bucketNum; i++) { buckets.add(new ArrayList<>()); } //将每个元素放到桶中 for (int cur : arr) { int index = (cur - min) / arr.length; // int index = (cur - min); //每个桶中只有一个元素的时候就是计数排序 buckets.get(index).add(cur); } //对每个桶内的元素进行排序,可以使用直接插入排序等排序方法 int index = 0; for (List<Integer> bucket : buckets) { insertSort(bucket); for (int cur : bucket) { arr[index++] = cur; } } return arr; } private static void insertSort(List<Integer> bucket) { Integer[] arr = bucket.toArray(new Integer[bucket.size()]); for (int i = 1; i < arr.length; i++) { for (int j = i - 1; j >= 0 && arr[j] > arr[j + 1]; j--) { swap(arr, j, j + 1); } } for (int i = 0; i < arr.length; i++) { bucket.set(i, arr[i]); } } }
4.2基数排序
算法思想: 基数排序(Radix Sort)是一种非比较型排序算法,它将整数按位数切割成不同的数字,然后按每个位分别进行排序。
基数排序的方式可以采用MSD(Most significant digital)或LSD(Least significant digital),MSD是从最高有效位开始排序,而LSD是从最低有效位开始排序。当然我们可以采用MSD方式排序,按最高有效位进行排序,将最高有效位相同的放到一堆,然后再按下一个有效位对每个堆中的数递归地排序,最后再将结果合并起来。但是,这样会产生很多中间堆(高位排序比低位排序多了空间开销)。所以,通常基数排序采用的是LSD方式。LSD基数排序实现的基本思路是将所有待比较数值(正整数)统一为同样的数位长度,数位较短的数前面补零。然后,从最低位开始,依次进行一次排序。这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列。
需要注意的是,对每一个数位进行排序的算法必须是稳定的,否则就会取消前一次排序的结果。
稳定性:稳定
复杂度分析:设待排序列为n个记录,d个关键码,关键码的取值范围为radix,则进行链式基数排序的时间复杂度为O(d(n+radix)),其中,一趟分配时间复杂度为O(n),一趟收集时间复杂度为O(radix),共进行d趟分配和收集。
空间效率:需要2*radix个指向队列的辅助空间,以及用于静态链表的n个指针。
算法实现:
public class NoCompare_RadixSort { public static int[] radixSort(int[] arr) { int maxLen = getMaxBit(arr);//得到arr中最大的数的长度 int[] tmp = new int[arr.length]; int[] count = new int[10];// 计数器 int radix = 1; for (int i = 1; i <= maxLen; i++) {// 进行maxLen次排序 Arrays.fill(count, 0);// 每次分配前清空计数器 for (int j = 0; j < arr.length; j++) { int k = (arr[j] / radix) % 10;// 统计每个桶中的记录数 count[k]++; } for (int j = 1; j < 10; j++) { count[j] = count[j - 1] + count[j];// 将tmp中的位置依次分配给每个桶 } for (int j = arr.length - 1; j != -1; j--) {// 将所有桶中的记录依次收集到tmp中 int k = (arr[j] / radix) % 10; tmp[count[k] - 1] = arr[j]; count[k]--; } for (int j = 0; j < arr.length; j++) {// 将临时数组的内容复制到arr中 arr[j] = tmp[j]; } radix = radix * 10; } return arr; } // 得到arr中最大的数的长度 private static int getMaxBit(int[] arr) { int maxNum = Integer.MIN_VALUE; for (int cur : arr) { maxNum = Math.max(maxNum, cur); } return String.valueOf(maxNum).length(); } }
(5)归并排序
算法思想:
将数组分成二组A,B,如果这二组组内的数据都是有序的,那么就可以很方便的将这二组数据进行合并。
可以将A,B组各自再分成二组。依次类推,当分出来的小组只有一个数据时,
可以认为这个小组组内已经达到了有序,然后再合并相邻的二个小组就可以了。这样通过先递归的分解数列,再合并数列就完成了归并排序。
稳定性:稳定
复杂度分析:最好、最坏、平均TC都是O(NlogN)。SC是O(N)
算法实现:
public class MergeSort { //将arr[first~mid]和arr[mid~last]合并到tmp中 private static void mergeArray(int[] arr, int first, int mid, int last, int[] tmp) { int begin1 = first; int begin2 = mid + 1; int end1 = mid; int end2 = last; int k = 0; while (begin1 <= end1 && begin2 <= end2) { if (arr[begin1] < arr[begin2]) { tmp[k++] = arr[begin1++]; } else { tmp[k++] = arr[begin2++]; } } while (begin1 <= end1) { tmp[k++] = arr[begin1++]; } while (begin2 <= end2) { tmp[k++] = arr[begin2++]; } //将辅助数组tmp的数据写回arr for (begin1 = 0; begin1 < k; begin1++) { arr[first + begin1] = tmp[begin1]; } } public static int[] mergeSort(int[] arr, int first, int last, int[] tmp) { if (first < last) { int mid = (first + last) / 2; mergeSort(arr, first, mid, tmp);//左边有序 mergeSort(arr, mid + 1, last, tmp);//右边有序 mergeArray(arr, first, mid, last, tmp);//将两个有序数列合并 } return arr; } }
此外,为了验证结果的正确性,可以写个和Arrays.sort()方法比较的代码。getIntArr得到一个大小是size,最大值小于bound的int数组。arrEquals比较两个int数组是否相等。
public class MyUtil { public static int[] getIntArr(int size, int bound) { int[] arr = new int[size]; Random r = new Random(); for (int i = 0; i < size; i++) { arr[i] = r.nextInt(bound); } return arr; } public static boolean arrEquals(int[] arr1, int[] arr2) { for (int i = 0; i < arr1.length; i++) { if (arr1[i] != arr2[i]) { return false; } } return true; } }
以直接插入排序为例,我们可以这么用MyUtil。
public static void main(String[] args) { int times = 0; while (times++ < 100) { int[] arr = MyUtil.getIntArr(50, 100); int[] brr = arr.clone(); Arrays.sort(arr); if (!MyUtil.arrEquals(arr, sis(brr))) { System.out.println("Something Wrong"); } } System.out.println("Everything is OK."); }