写点什么

Java 总结:各种排序算法的介绍及其之间的对比差异

  • 2022 年 5 月 01 日
  • 本文字数:4058 字

    阅读完需:约 13 分钟

buildMaxHeap(a, arrayLength - 1 - i);


//交换堆顶和最后一个元素


swap(a, 0, arrayLength - 1 - i);


printArray(" ",a);


}


}


private void swap(int[] data, int i, int j) {


int tmp = data[i];


data[i] = data[j];


data[j] = tmp;


}


//对 data 数组从 0 到 lastIndex 建大顶堆


private void buildMaxHeap(int[] data, int lastIndex) {


//从 lastIndex 处节点(最后一个节点)的父节点开始


for (int i = (lastIndex - 1) / 2; i >= 0; i--) {


//k 保存正在判断的节点


int k = i;


//如果当前 k 节点的子节点存在


while (k * 2 + 1 <= lastIndex) {


//k 节点的左子节点的索引


int biggerIndex = 2 * k + 1;


//如果 biggerIndex 小于 lastIndex,即 biggerIndex+1 代表的 k 节点的右子节点存在


if (biggerIndex < lastIndex) {


//若果右子节点的值较大


if (data[biggerIndex] < data[biggerIndex + 1]) {


//biggerIndex 总是记录较大子节点的索引


biggerIndex++;


}


}


//如果 k 节点的值小于其较大的子节点的值


if (data[k] < data[biggerIndex]) {


//交换他们


swap(data, k, biggerIndex);


//将 biggerIndex 赋予 k,开始 while 循环的下一次循环,重新保证 k 节点的值大于其左右子节点的值


k = biggerIndex;


} else {


break;


}


}


}


}


public static void main(String[] args) {


HeapSort hs = new HeapSort ();


}


}

六、冒泡排序

  1. 基本思想:在要排序的一组数中,对当前还未排好序的范围内的全部数,


自上而下对相邻的两个数依次进行比较和调整,让较大的数往下沉,较小的往上冒。


即:每当两相邻的数比较后发现它们的排序与排序要求相反时,就将它们互换。


  1. 实例:第 0 次下沉的数是 9,第 1 次下沉的数是 8 …



  1. 用 Java 实现


public void bubbleSort() {


int[] a = new int[]{9, 8, 7, 6, 5, 4, 3, 2, 1, 0};


printArray("数 组: ", a);


int temp;


for (int i = 0; i < a.length - 1; i++) {


for (int j = 0; j < a.length - 1 - i; j++) {


if (a[j] > a[j + 1]) {


temp = a[j];


a[j] = a[j + 1];


a[j + 1] = temp;


}


}


printArray("第" + i + "步:", a);


}


printArray("冒泡排序结果: ", a);


}

七、快速排序

  1. 基本思想:选择一个基准元素,通常选择第一个元素或者最后一个元素,


通过一趟扫描,将待排序列分成两部分,一部分比基准元素小,一部分大于等于基准元素,


此时基准元素在其排好序后的正确位置,然后再用同样的方法递归地排序划分的两部分。


  1. 实例



  1. 用 Java 实现


public class QuickSort {


public void execute() {


int[] a = {5, 2, 3, 6, 1, 8, 0, 9, 7, 4};


printArray("\n 排序前 ", a);


quick(a);


printArray("排序后 ", a);


}


// 分成两断后返回中轴的位置


public int getMiddle(int[] list, int low, int high) {


int tmp = list[low]; //数组的第一个作为中轴


while (low < high) {


while (low < high && list[high] >= tmp) {


high--;


}


list[low] = list[high]; //比中轴小的记录移到低端


while (low < high && list[low] <= tmp) {


low++;


}


list[high] = list[low]; //比中轴大的记录移到高端


}


list[low] = tmp; //中轴记录到尾


printArray(" ",list);


return low; //返回中轴的位置


}


public void _quickSort(int[] b, int low, int high) {


if (low < high) {


int middle = getMiddle(b, low, high); //将 list 数组进行一分为二


_quickSort(b, low, middle - 1); //对低字表进行递归排序


_quickSort(b, middle + 1, high); //对高字表进行递归排序


}


}


public void quick(int[] a) {


if (a.length > 0) { //查看数组是否为空


_quickSort(a, 0, a.length - 1);


}


}


public static void main(String[] args) {


QuickSort qs = new QuickSort();


qs.execute();


}


}

八、归并排序

  1. 基本思想:归并(Merge)排序法是将两个(或两个以上)有序表合并成一个新的有序表,


即把待排序序列分为若干个子序列,每个子序列是有序的。


然后再把有序子序列合并为整体有序序列。


  1. 实例



  1. 用 Java 实现


public class MergeSort {


public void execute() {


int a[] = {5, 2, 3, 6, 1, 8, 0, 9, 7, 4};


printArray("\n 排序前:", a);


sort(a, 0, a.length - 1);


printArray("排序后:", a);


}


public void sort(int[] data, int left, int right) {


if (left < right) {


//找出中间索引


int center = (left + right) / 2;


//对左边数组进行递归


sort(data, left, center);


//对右边数组进行递归


sort(data, center + 1, right);


//合并


merge(data, left, center, right);


}


}


public void merge(int[] data, int left, int center, int right) {


int[] tmpArr = new int[data.length];


int mid = center + 1;


//third 记录中间数组的索引


int third = left;


int tmp = left;


while (left <= center && mid <= right) {


//从两个数组中取出最小的放入中间数组


if (data[left] <= data[mid]) {


tmpArr[third++] = data[left++];


} else {


tmpArr[third++] = data[mid++];


}


}


//剩余部分依次放入中间数组


while (mid <= right) {


tmpArr[third++] = data[mid++];


}


while (left <= center) {


tmpArr[third++] = data[left++];


}


//将中间数组中的内容复制回原数组


while (tmp <= right) {


data[tmp] = tmpArr[tmp++];


}


printArray(" ", data);


}


public static void main(String[] args) {


MergeSort ms= new MergeSort();


ms.execute();


}


}

九、基数排序

  1. 基本思想:将所有待比较数值(正整数)统一为同样的数位长度,数位较短的数前面补零。


然后,从最低位开始,依次进行一次排序。


这样从最低位排序一直到最高位排序完成以后,数列就变成一个有序序列。


  1. 实例 《一线大厂 Java 面试题解析+后端开发学习笔记+最新架构讲解视频+实战项目源码讲义》无偿开源 威信搜索公众号【编程进阶路】




  1. 用 Java 实现


import java.util.ArrayList;


import java.util.List;


public class RadixSort {


public void execute() {


int a[] = {135,242,192,93,345,11,24,19};


printArray("\n 排序前:", a);


sort(a);


printArray("排序后:", a);


}


public void sort(int[] array) {


//首先确定排序的趟数;


int max = array[0];


for (int i = 1; i < array.length; i++) {


if (array[i] > max) {


max = array[i];


}


}


int time = 0;


//判断位数;


while (max > 0) {


max /= 10;


time++;


}


//建立 10 个队列;


List<ArrayList> queue = new ArrayList<ArrayList>();


for (int i = 0; i < 10; i++) {


ArrayList<Integer> queue1 = new ArrayList<Integer>();


queue.add(queue1);


}


//进行 time 次分配和收集;


for (int i = 0; i < time; i++) {


//分配数组元素;


for (int j = 0; j < array.length; j++) {


//得到数字的第 time+1 位数;


int x = array[j] % (int) Math.pow(10, i + 1) / (int) Math.pow(10, i);


ArrayList<Integer> queue2 = queue.get(x);


queue2.add(array[j]);


queue.set(x, queue2);


}


int count = 0;//元素计数器;


//收集队列元素;


for (int k = 0; k < 10; k++) {


while (queue.get(k).size() > 0) {


ArrayList<Integer> queue3 = queue.get(k);


array[count] = queue3.get(0);


queue3.remove(0);


count++;


}


}


}


}


public static void main(String[] args) {


RadixSort rs = new RadixSort();


rs.execute();


}


}

十、各种排序算法的分析

直接插入排序
  • 直接插入排序是稳定的排序。

  • 关于各种算法的稳定性分析可以[参考文章](()

  • 文件初态不同时,直接插入排序所耗费的时间有很大差异。若文件初态为正序,则每个待插入的记录只需要比较一次就能够找到合适的位置插入,故算法的时间复杂度为 O(n),这时最好的情况。若初态为反序,则第 i 个待插入记录需要比较 i+1 次才能找到合适位置插入,故时间复杂度为 O(n2),这时最坏的情况。

  • 直接插入排序的平均时间复杂度为 O(n2)。

二分法插入排序(按二分法找到合适位置插入)
  • 当然,二分法插入排序也是稳定的。

  • 二分法插入排序的思想和直接插入一样,只是找合适的插入位置的方式不同,这里是按二分法找到合适的位置,可以减少比较的次数。

  • 二分插入排序的比较次数与待排序记录的初始状态无关,仅依赖于记录的个数。当 n 较大时,比直接插入排序的最大比较次数少得多。但大于直接插入排序的最小比较次数。

  • 算法的移动次数与直接插入排序算法的相同,最坏的情况为 n2/2,最好的情况为 n,平均移动次数为 O(n2)。

希尔排序
  • 我们知道一次插入排序是稳定的,但在不同的插入排序过程中,相同的元素可能在各自的插入排序中移动,最后其稳定性就会被打乱,所以希尔排序是不稳定的。

  • 希尔排序的时间性能优于直接插入排序,原因如下:

  • 当文件初态基本有序时直接插入排序所需的比较和移动次数均较少。

  • 当 n 值较小时,n 和 n2 的差别也较小,即直接插入排序的最好时间复杂度 O(n)和最坏时间复杂度 0(n2)差别不大。

  • 在希尔排序开始时增量较大,分组较多,每组的记录数目少,故各组内直接插入较快,后来增量 di 逐渐缩小,分组数逐渐减少,而各组的记录数目逐渐增多,但由于已经按 di-1 作为距离排过序,使文件较接近于有序状态,所以新的一趟排序过程也较快。

  • 因此,希尔排序在效率上较直接插人排序有较大的改进。

  • 希尔排序的平均时间复杂度为 O(nlogn)。

选择排序
  • 简单选择排序是不稳定的排序。

  • 时间复杂度:T(n)=O(n2)。

堆排序
  • 堆排序也是一种不稳定的排序算法。

  • 堆排序优于简单选择排序的原因:

  • 直接选择排序中,为了从 R[1..n]中选出关键字最小的记录,必须进行 n-1 次比较,然后在 R[2..n]中选出关键字最小的记录,又需要做 n-2 次比较。事实上,后面的 n-2 次比较中,有许多比较可能在前面的 n-1 次比较中已经做过,但由于前一趟排序时未保留这些比较结果,所以后一趟排序时又重复执行了这些比较操作。

  • 堆排序可通过树形结构保存部分比较结果,可减少比较次数。

  • 堆排序的最坏时间复杂度为 O(nlogn)。堆序的平均性能较接近于最坏性能。由于建初始堆所需的比较次数较多,所以堆排序不适宜于记录数较少的文件。

冒泡排序
  • 冒泡排序是一种稳定的排序方法。

  • 若文件初状为正序,则一趟起泡就可完成排序,排序码的比较次数为 n-1,且没有记录移动,时间复杂度是 O(n)

  • 若文件初态为逆序,则需要 n-1 趟起泡,每趟进行 n-i 次排序码的比较,且每次比较都移动三次,比较和移动次数均达到最大值∶O(n2)

  • 起泡排序平均时间复杂度为 O(n2)

用户头像

还未添加个人签名 2022.04.13 加入

还未添加个人简介

评论

发布
暂无评论
Java 总结:各种排序算法的介绍及其之间的对比差异_Java_爱好编程进阶_InfoQ写作社区