Java十大排序算法怎么实现

2023-05-28 02:19| 来源: 网络整理| 查看: 265

Java十大排序算法怎么实现

排序算法的稳定性：

假定在待排序的记录序列中，存在多个具有相同的关键字的记录，如果排序以后，保证这些记录的相对次序保持不变，即在原序列中，a[i]=a[j]，且 a[i] 在 a[j] 之前，排序后保证 a[i] 仍在 a[j] 之前，则称这种排序算法是稳定的；否则称为不稳定的。

Java十大排序算法怎么实现

一.选择排序

每次从待排序的元素中选择最小的元素，依次和第1、2、3...位置的元素进行交换。这样在数组前面的部分形成有序区域。每进行一次交换，有序区域长度加一。

Java十大排序算法怎么实现

public static void selectionSort(int[] arr){ //细节一：这里可以是arr.length也可以是arr.length-1 for (int i = 0; i < arr.length-1 ; i++) { int mini = i; for (int j = i+1; j < arr.length; j++) { //切换条件，决定升序还是降序 if(arr[mini]>arr[j]) mini =j; } swap(arr,mini,i); } }登录后复制二.冒泡排序

依次比较相邻的两个数，如果顺序错误就把他们交换过来，这样的话，每一轮比较下来都可以把最大的数放到它应该在的位置。（就像是把最大的气泡冒到最上层一样）

这里解释一下顺序错误的含义。我们按照按升序排序，后面的值应该大于等于前面的值，如果不满足的话，就交换。

Java十大排序算法怎么实现

public static void bubbleSort(int[] arr){ for (int i = 0; i < arr.length-1; i++) { //记录本次有没有进行交换的操作 boolean flag = false; //保存在头就动头，保存在尾就动尾 for(int j =0 ; j < arr.length-1-i ; j++){ //升序降序选择地 if(arr[j] > arr[j+1]) { swap(arr,j,j+1); flag = true; } } //如果本次没有进行交换操作，表示数据已经有序 if(!flag){break;} //程序结束 } }登录后复制三.插入排序

插入排序其实可以理解为我们玩扑克时摸牌的过程，我们在摸牌的时候手里的牌总是有序的，每摸一张牌，就把这张牌插到它应该在的位置。等所有的牌都摸完了以后，全部的牌就都有序了。

Java十大排序算法怎么实现

思考：数组前面形成了有序区域，那我查找当前数字应该插入位置的时候，用二分进行，是不是就可以把插入排序的复杂度优化到O(nlogn)了呀？

二分倒是可以log的复杂度找到位置。关键是如果用数组存储的话，插入的时候数据后移还是O(n)的复杂度。如果用链表的话，找到位置插入是O(1)的了，但是链表也没办法二分呀。

public static void insertSort(int[] arr){ //从第二个数开始，把每个数依次插入到指定的位置 for(int i = 1 ; i < arr.length ; i++) { int key = arr[i]; int j = i-1; //大的后移操作 while(j >= 0 && arr[j] > key) { arr[j+1] = arr[j]; j--; } arr[j+1] = key; } }登录后复制四.希尔排序

希尔排序是Donald Shell于1959年提出的一种排序算法，是对直接插入排序的改进之后的高效版本。希尔排序需要准备一组数据作为增量序列。

这组数据需要满足以下三个条件：

1. 数据递减排列

2. 数据中的最大值小于待排序数组的长度

3. 数据中的最小值是1。

只要满足上述要求的数组都可以作为增量序列，但是不同的增量序列会影响到排序的效率。这里我们用{5,3,1}作为增量序列来进行讲解

Java十大排序算法怎么实现

实现优化的原因：减少数据量，使O(n)和O(n^2)的差距并不大

public static void shellSort(int[] arr){ //分块处理 int gap = arr.length/2; //增量 while(1= 0 && arr[j] > key) { arr[j+gap] = arr[j]; j-=gap; } arr[j+gap] = key; } gap = gap/2; } }登录后复制五.堆排序

是一棵完全二叉树，分为大根堆、小根堆两种

可以O(1)取最大/小值，可以O(logn)删除最大/小值，可以O(logn)插入元素

MIN-HEAPIFY（i）操作：

我们假设完全二叉树中某节点 i 的左子树和右子树都满足小根堆的性质，假设 i 节点的左孩子是 left_i，i 节点的右孩子是 rigℎt_i。那如果 a[i] 大于 a[left_i] 或 a[rigℎt_i] 的话，那以 i 节点为根节点的整棵子树就不满足小根堆的性质了，我们现在要进行一个操作：把以 i 为根节点的这棵子树调整成小根堆。

Java十大排序算法怎么实现

//堆排序 public static void heapSort(int[] arr){ //开始调整的位置为最后一个叶子节点 int start = (arr.length - 1)/2; //从最后一个叶子节点开始遍历，调整二叉树 for (int i = start; i >= 0 ; i--){ maxHeap(arr, arr.length, i); } for (int i = arr.length - 1; i > 0; i--){ int temp = arr[0]; arr[0] = arr[i]; arr[i] = temp; maxHeap(arr, i, 0); } } //将二叉树调整为大顶堆 public static void maxHeap(int[] arr, int size, int index){ //建立左子节点 int leftNode = 2 * index + 1; //建立右子节点 int rightNode = 2 * index + 2; int maxNode = index; //左子节点的值大于根节点时调整 if (leftNode < size && arr[leftNode] > arr[maxNode]){ maxNode = leftNode; } //右子节点的值大于根节点时调整 if (rightNode < size && arr[rightNode] > arr[maxNode]){ maxNode = rightNode; } if (maxNode != index){ int temp = arr[maxNode]; arr[maxNode] = arr[index]; arr[index] = temp; //交换之后可能会破坏原来的结构，需要再次调整 //递归调用进行调整 maxHeap(arr, size, maxNode); } }登录后复制

我使用的是大根堆，排序的过程归根下来就是：先左底根后右底根（看自己怎么写）->每个根向上在向下。（左右上下）

六.归并排序

归并排序是分治法的典型应用，先来介绍一下分治法，分治法是把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题……直到最后子问题规模很小可以直接求解，再将子问题的解进行合并来得到原问题的解。

Java十大排序算法怎么实现

归并排序分解子问题的过程就是每一次把数组分成2份，直到数组的长度为1（因为只有一个数字的数组是有序的）。然后再将相邻的有序数组合并成一个有序数组。直到全部合到一起，整个数组就排序完毕了。现在要解决的问题就是如何把两个有序的数组合并成一个有序的数组。其实就是每次比较两个数组当前最小的两个元素，哪个小就选哪个

数组a

数组b

说明

答案数组

2,5,7

1,3,4

【本文地址】

Java十大排序算法怎么实现

Java十大排序算法怎么实现

今日新闻

推荐新闻