安科网

java实现12种排序算法

yimixgg

yimixgg

2019-01-06

关注 关注

一．冒泡排序及其实现

二．希尔排序及其实现

三．插入排序及其实现

四．插入排序及其实现

五．快速排序及其实现

六．合并排序及其实现

七．计数排序及其实现

八．基数排序及其实现

九． 桶排序及其实现

十． 堆排序及其实现

十一.二叉树排序及有序集合

十二.利用集合的4种排序排序方式

一．冒泡排序及其实现

一．home→包

BubbleSort→类

main→主函数

bubbleSort1()→冒泡排序1

bubbleSort2()→冒泡排序优化1

bubbleSort3()→冒泡排序优化2

java实现12种排序算法

1 package home;
 2 import java.util.Arrays;
 3 
 4 /**
 5 * 冒泡排序的三种写法
 6 * @author Stringer123
 7 * @version 1.0
 8 * 
 9 */
10 public class BubbleSort {
11 
12 public static void main(String[] args) {
13 // TODO Auto-generated method stub
14 int[] arr = { 1, 1, 2, 0, 9, 3, 12, 7, 8, 3, 4, 65, 22 };
15 // int[] b1 = bubbleSort1(arr);
16 // int[] b1 = bubbleSort2(arr);
17 int[] b1 = bubbleSort3(arr);
18 
19 // 遍历方式1：java 8新特性（利用Lambda表达式）→通过转成流输出数组
20 Arrays.stream(b1).forEach(item -> {
21 System.out.print(item + " ");
22 });
23 System.out.println();
24 
25 // 遍历方式2:通过传统for循环遍历
26 for (int i = 0; i < b1.length; i++) {
27 System.out.print(b1[i] + " ");
28 }
29 System.out.println();
30 
31 // 遍历方式3:通过增强for循环遍历（也成for-each循环）
32 for (int i : b1) {
33 System.out.print(i + " ");
34 }
35 System.out.println();
36 }

java实现12种排序算法

(1) 冒泡排序的第一种实现，没有任何优化

java实现12种排序算法

private static int[] bubbleSort1(int[] a) {
 System.out.println("bubbleSort1的排序结果：");
 int i, j;
 int n = a.length;
 for (i = 0; i < n; i++) {
 for (j = 1; j < n - i; j++) { // 前面的数字大于后面的数字就交换
 if (a[j - 1] > a[j]) { // 交换a[j-1]和a[j]
 int temp;
 temp = a[j - 1];
 a[j - 1] = a[j];
 a[j] = temp;
 }
 }
 }
 return a;
 }

java实现12种排序算法

(2) 冒泡排序的第一种优化实现

下面开始考虑优化，如果对于一个本身有序的序列，或则序列后面一大部分都是有序的序列，上面的算法就会浪费很多的时间开销，这里设置一个标志flag，如果这一趟发生了交换，则为true，否则为false。明显如果有一趟没有发生交换，说明排序已经完成。

java实现12种排序算法

/**
 * 设置一个标志，如果这一趟发生了交换，则为true，否则为false。明显如果有一趟没有发生交换，说明排序已经完成。
 * 
 * @param a
 * @return
 */
 private static int[] bubbleSort2(int[] a) {
 System.out.println("bubbleSort2的排序结果：");
 int j;
 int n = a.length;
 boolean flag = true;// 发生了交换就为true, 没发生就为false，第一次判断时必须标志位true。
 while (flag) {
 flag = false;// 每次开始排序前，都设置flag为未排序过
 for (j = 1; j < n; j++) {
 if (a[j - 1] > a[j]) {// 前面的数字大于后面的数字就交换
 // 交换a[j-1]和a[j]
 int temp;
 temp = a[j - 1];
 a[j - 1] = a[j];
 a[j] = temp;
 // 表示交换过数据;
 flag = true;
 }
 }
 n--;// 减小一次排序的尾边界
 } // end while
 return a;
 }

java实现12种排序算法

(3) 冒泡排序的第一种优化实现

再进一步做优化。比如，现在有一个包含1000个数的数组，仅前面100个无序，后面900个都已排好序且都大于前面100个数字，那么在第一趟遍历后，最后发生交换的位置必定小于100，且这个位置之后的数据必定已经有序了，也就是这个位置以后的数据不需要再排序了，于是记录下这位置，第二次只要从数组头部遍历到这个位置就可以了。如果是对于上面的冒泡排序算法2来说，虽然也只排序100次，但是前面的100次排序每次都要对后面的900个数据进行比较，而对于现在的排序算法3，只需要有一次比较后面的900个数据，之后就会设置尾边界，保证后面的900个数据不再被排序。

java实现12种排序算法

/**
 * 设置一个标志，如果这一趟发生了交换，则为true，否则为false。明显如果有一趟没有发生交换，说明排序已经完成。
 * 
 * @param a
 * @return
 *
 */
 public static int[] bubbleSort3(int[] a) {
 System.out.println("bubbleSort3的排序结果：");
 int j;
 int n = a.length;
 boolean flag = true;// 发生了交换就为true, 没发生就为false，第一次判断时必须标志位true。
 while (flag) {
 flag = false;// 每次开始排序前，都设置flag为未排序过
 for (j = 1; j < n; j++) {
 if (a[j - 1] > a[j]) {// 前面的数字大于后面的数字就交换
 // 交换a[j-1]和a[j]
 int temp;
 temp = a[j - 1];
 a[j - 1] = a[j];
 a[j] = temp;
 // 表示交换过数据;
 flag = true;
 }
 }
 n--;// 减小一次排序的尾边界
 } // end while
 return a;
 }// end
}

java实现12种排序算法

(4) 三种方法console输出显示：

java实现12种排序算法

java实现12种排序算法

java实现12种排序算法

二．希尔排序及其实现

（1）基本思想

先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，列中的记录“基本有序”时，再对全体记录进行依次直接插入排序。

（2）操作方法

1. 选择一个增量序列t1，t2，…，tk，其中ti>tj，tk=1；

2. 按增量序列个数k，对序列进行k 趟排序；

3. 每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m 的子序列，分别对各子表进行直接插入排序。仅增量因子为1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。

（3）希尔排序示例

java实现12种排序算法

（4）希尔排序代码实现

java实现12种排序算法

package home;
import java.util.Arrays;
public class ShellSort {
 /**希尔排序的原理:根据需求，如果你想要结果从大到小排列，它会首先将数组进行分组，然后将较大值移到前面，较小值
 * 移到后面，最后将整个数组进行插入排序，这样比起一开始就用插入排序减少了数据交换和移动的次数，可以说希尔排序是加强
 * 版的插入排序
 * 拿数组5, 2, 8, 9, 1, 3，4来说，数组长度为7，当increment为3时，数组分为两个序列
 * 5，2，8和9，1，3，4，第一次排序，9和5比较，1和2比较，3和8比较，4和比其下标值小increment的数组值相比较
 * 此例子是按照从大到小排列，所以大的会排在前面，第一次排序后数组为9, 2, 8, 5, 1, 3，4
 * 第一次后increment的值变为3/2=1,此时对数组进行插入排序，
 *实现数组从大到小排
 */
 public static void main(String[] args) {
 // TODO Auto-generated method stub
 int[] arr = { 5, 2, 8, 9, 1, 3,4 };
 int[] b1 = shellSort(arr);
 System.out.println("shellSort排序结果：");
 Arrays.stream(b1).forEach(item -> {
 System.out.print(item + " ");
 });
 }
 private static int[] shellSort(int[] a) {
 // TODO Auto-generated method stub
 int j = 0;
 int temp = 0;
 // 每次将步长缩短为原来的一半,increment为步长
 for (int increment = a.length / 2; increment > 0; increment /= 2) {
 for (int i = increment; i < a.length; i++) {
 temp = a[i];
 for (j = i; j >= increment; j -= increment) {
 if (temp > a[j - increment])// 如想从小到大排只需修改这里
 {
 a[j] = a[j - increment];
 } else {
 break;
 }
 }
 a[j] = temp;
 }
 }
 return a;
 }
}

java实现12种排序算法

（5）控制台输出结果：

java实现12种排序算法

三．插入排序及其实现

（1）插入排序代码实现：

java实现12种排序算法

package home;
import java.util.Arrays;
public class InsertSort {
 /**
 * 插入排序
 * 
 * 从第一个元素开始，该元素可以认为已经被排序 取出下一个元素，在已经排序的元素序列中从后向前扫描
 * 如果该元素（已排序）大于新元素，将该元素移到下一位置 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置 将新元素插入到该位置中 重复步骤2
 * 
 * @param numbers
 * 待排序数组
 */
 public static void main(String[] args) {
 int[] arr = { 1, 1, 2, 0, 9, 3, 12, 7, 8, 3, 4, 65, 22 };
 int[] b1 = insertSort(arr);
 
 System.out.println("insertSort排序结果：");
 Arrays.stream(b1).forEach(item -> {System.out.print(item + " ");});
 }
 private static int[] insertSort(int[] a) {
 int n = a.length;
 int temp = 0;
 int j = 0;
 for (int i = 0; i < n; i++) {
 temp = a[i];
 // 假如temp比前面的值小，则将前面的值后移
 for (j = i; j > 0 && temp < a[j - 1]; j--) {
 a[j] = a[j - 1];
 }
 a[j] = temp;
 }
 return a;
 }
}

java实现12种排序算法

（2）控制台输出结果：

java实现12种排序算法

四．插入排序及其实现

（1）选择排序代码实现

java实现12种排序算法

package home;
public class ChooseSort {
 public static void main(String[] args) {
 // TODO Auto-generated method stub
 int[] arr = { 1, 3, 2, 45, 65, 33, 12 };
 int n = arr.length;
 // 选择排序的优化
 for (int i = 0; i < n - 1; i++) {// 做第i趟排序
 int k = i;
 for (int j = k + 1; j < n; j++) {// 选最小的记录
 if (arr[j] < arr[k]) {
 k = j; // 记下目前找到的最小值所在的位置
 }
 }
 // 在内层循环结束，也就是找到本轮循环的最小的数以后，再进行交换
 if (i != k) { // 交换a[i]和a[k]
 int temp = arr[i];
 arr[i] = arr[k];
 arr[k] = temp;
 }
 }
 for (int num : arr) {
 System.out.print(num + " ");
 }
 }
}

java实现12种排序算法

（2）控制台输出结果：

java实现12种排序算法

五．快速排序及其实现

一．快速排序1：//固定的切分方式

java实现12种排序算法

package home;
public class ChooseSort {
 public static void main(String[] args) {
 // TODO Auto-generated method stub
 System.out.println("chooseSort排序结果：");
 int[] arr = { 1, 3, 2, 45, 65, 33, 12 };
 int n = arr.length;
 // 选择排序的优化
 for (int i = 0; i < n - 1; i++) {// 做第i趟排序
 int k = i;
 for (int j = k + 1; j < n; j++) {// 选最小的记录
 if (arr[j] < arr[k]) {
 k = j; // 记下目前找到的最小值所在的位置
 }
 }
 // 在内层循环结束，也就是找到本轮循环的最小的数以后，再进行交换
 if (i != k) { // 交换a[i]和a[k]
 int temp = arr[i];
 arr[i] = arr[k];
 arr[k] = temp;
 }
 }
 for (int num : arr) {
 System.out.print(num + " ");
 }
 }
}

java实现12种排序算法

输出结果：

java实现12种排序算法

二．快速排序的优化

java实现12种排序算法

package home;
//对于基准位置的选取：随机切分和三取样切分。固定切分的效率并不是太好，随即切分是常用的一种切分，效率比较高，最坏情况下复杂度有可能为O(N^2)，对于三数取中选择基准点是最理想的一种.
public class QuickSort1 {
 public static void main(String[] args) {
 // TODO Auto-generated method stub
 System.out.println("快速排序优化算法：");
 int[] a = {12,20,5,16,15,1,30,45,23,9};
 int start = 0;
 int end = a.length-1;
 sort(a,start,end);
 for(int i = 0; i<a.length; i++){
 System.out.print(a[i]+" ");
 }
 }
 public static int partition(int []array,int lo,int hi){
 //三数取中
 int mid=lo+(hi-lo)/2;
 if(array[mid]>array[hi]){
 swap(array[mid],array[hi]);
 }
 if(array[lo]>array[hi]){
 swap(array[lo],array[hi]);
 }
 if(array[mid]>array[lo]){
 swap(array[mid],array[lo]);
 }
 int key=array[lo];
 
 while(lo<hi){
 while(array[hi]>=key&&hi>lo){
 hi--;
 }
 array[lo]=array[hi];
 while(array[lo]<=key&&hi>lo){
 lo++;
 }
 array[hi]=array[lo];
 }
 array[hi]=key;
 return hi;
 }
 
 public static void swap(int a,int b){
 int temp=a;
 a=b;
 b=temp;
 }
 public static void sort(int[] array,int lo ,int hi){
 if(lo>=hi){
 return ;
 }
 int index=partition(array,lo,hi);
 sort(array,lo,index-1);
 sort(array,index+1,hi);
 }
}

java实现12种排序算法

输出结果：

java实现12种排序算法

六．合并排序及其实现

（1）合并排序代码实现

java实现12种排序算法

package home;
public class MergeSort {
 public static void main(String[] args) {
 // TODO Auto-generated method stub
 System.out.println("合并排序算法：");
 int[] a = {12,20,5,16,15,1,30,45,23,9};
 int start = 0;
 int end = a.length-1;
 sort(a,start,end);
 for(int i = 0; i<a.length; i++){
 System.out.print(a[i]+" ");
 }
 }
 public static int[] sort(int[] a, int low, int high) {
 int mid = (low + high) / 2;
 if (low < high) {
 sort(a, low, mid);
 sort(a, mid + 1, high);
 // 左右归并
 merge(a, low, mid, high);
 }
 return a;
 }
 public static void merge(int[] a, int low, int mid, int high) {
 int[] temp = new int[high - low + 1];
 int i = low;
 int j = mid + 1;
 int k = 0;
 // 把较小的数先移到新数组中
 while (i <= mid && j <= high) {
 if (a[i] < a[j]) {
 temp[k++] = a[i++];
 } else {
 temp[k++] = a[j++];
 }
 }
 // 把左边剩余的数移入数组
 while (i <= mid) {
 temp[k++] = a[i++];
 }
 // 把右边边剩余的数移入数组
 while (j <= high) {
 temp[k++] = a[j++];
 }
 // 把新数组中的数覆盖nums数组
 for (int x = 0; x < temp.length; x++) {
 a[x + low] = temp[x];
 }
 }
}

java实现12种排序算法

（2）控制台输出结果：

java实现12种排序算法

七．计数排序及其实现

（1）计数排序代码实现

java实现12种排序算法

package home;
import java.util.Arrays;
public class CountingSort {
 public static void main(String[] args) {
 // TODO Auto-generated method stub
 int[] arr = { 1, 1, 2, 0, 9, 3, 12, 7, 8, 3, 4, 65, 22 };
 int[] b1 = CountingSort(arr);
 System.out.println("基计数排序结果：");
 Arrays.stream(b1).forEach(item -> {
 System.out.print(item + " ");
 });
 }
 public static int[] CountingSort(int[] array) {
 if (array.length == 0) return array;
 int bias, min = array[0], max = array[0];
 for (int i = 1; i < array.length; i++) {
 if (array[i] > max)
 max = array[i];
 if (array[i] < min)
 min = array[i];
 }
 bias = 0 - min;
 int[] bucket = new int[max - min + 1];
 Arrays.fill(bucket, 0);
 for (int i = 0; i < array.length; i++) {
 bucket[array[i] + bias]++;
 }
 int index = 0, i = 0;
 while (index < array.length) {
 if (bucket[i] != 0) {
 array[index] = i - bias;
 bucket[i]--;
 index++;
 } else
 i++;
 }
 return array;
 }
}

java实现12种排序算法

（2）控制台输出结果

java实现12种排序算法

八．基数排序及其实现

（1）基数排序

基数排序也是非比较的排序算法，对每一位进行排序，从最低位开始排序，复杂度为O(kn),为数组长度，k为数组中的数的最大的位数；

基数排序是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。有时候有些属性是有优先级顺序的，先按低优先级排序，，再按高优先级排序。最后的次序就是高优先级高的在前，高优先级相同的低优先级高的在前。基数排序基于分别排序，分别收集，所以是稳定的

（2）算法描述

1.取得数组中的最大数，并取得位数。

2. arr为原始数组，从最低位开始取每个位组成radix数组。

3. 对radix进行计数排序（利用计数排序适用于小范围数的特点）。

（3）基数排序代码实现

java实现12种排序算法

package home;
import java.util.ArrayList;
import java.util.Arrays;
public class RadixSort {
 public static void main(String[] args) {
 // TODO Auto-generated method stub
 int[] arr = { 1, 1, 2, 0, 9, 3, 12, 7, 8, 3, 4, 65, 22 };
 int[] b1 = RadixSort(arr);
 System.out.println("基数排序结果：");
 Arrays.stream(b1).forEach(item -> {
 System.out.print(item + " ");
 });
 }
 public static int[] RadixSort(int[] array) {
 if (array == null || array.length < 2)
 return array;
 // 1.先算出最大数的位数；
 int max = array[0];
 for (int i = 1; i < array.length; i++) {
 max = Math.max(max, array[i]);
 }
 int maxDigit = 0;
 while (max != 0) {
 max /= 10;
 maxDigit++;
 }
 int mod = 10, div = 1;
 ArrayList<ArrayList<Integer>> bucketList = new ArrayList<ArrayList<Integer>>();
 for (int i = 0; i < 10; i++)
 bucketList.add(new ArrayList<Integer>());
 for (int i = 0; i < maxDigit; i++, mod *= 10, div *= 10) {
 for (int j = 0; j < array.length; j++) {
 int num = (array[j] % mod) / div;
 bucketList.get(num).add(array[j]);
 }
 int index = 0;
 for (int j = 0; j < bucketList.size(); j++) {
 for (int k = 0; k < bucketList.get(j).size(); k++)
 array[index++] = bucketList.get(j).get(k);
 bucketList.get(j).clear();
 }
 }
 return array;
 }
}

java实现12种排序算法

（4）控制台输出结果

java实现12种排序算法

九．桶排序及其实现

（1）桶排序代码实现

java实现12种排序算法

package home;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Iterator;
import java.util.List;
public class BucketSort {
 public static void main(String[] args) {
 // TODO Auto-generated method stub
 int[] arr = { 1, 1, 2, 0, 9, 3, 12, 7, 8, 3, 4, 65, 22 };
 ArrayList <Integer> n = new ArrayList<Integer>();
 for(int i=0;i<arr.length;i++){
 n.add(arr[i]);
 }
 System.out.println("桶排序后的结果");
 ArrayList resultArr=BucketSort(n, arr.length);
 
 //遍历方式1
 System.out.println("遍历方式1：");
 Iterator it1 = resultArr.iterator();
 while(it1.hasNext()){
 System.out.print(it1.next()+" ");
 }
 
 //遍历方式2
 System.out.println();
 System.out.println("遍历方式2：");
 for(Iterator it2 = resultArr.iterator();it2.hasNext();){
 System.out.print(it2.next()+" ");
 }
 
 //遍历方式3
 System.out.println();
 System.out.println("遍历方式3：");
 for(int i = 0;i < resultArr.size(); i ++){
 System.out.print(resultArr.get(i)+" ");
 }
 
 }
 
 public static ArrayList<Integer> BucketSort(ArrayList<Integer> array, int bucketSize) {
 if (array == null || array.size() < 2)
 return array;
 int max = array.get(0), min = array.get(0);
 // 找到最大值最小值
 for (int i = 0; i < array.size(); i++) {
 if (array.get(i) > max)
 max = array.get(i);
 if (array.get(i) < min)
 min = array.get(i);
 }
 int bucketCount = (max - min) / bucketSize + 1;
 ArrayList<ArrayList<Integer>> bucketArr = new ArrayList<>(bucketCount);
 ArrayList<Integer> resultArr = new ArrayList<>();
 for (int i = 0; i < bucketCount; i++) {
 bucketArr.add(new ArrayList<Integer>());
 }
 for (int i = 0; i < array.size(); i++) {
 bucketArr.get((array.get(i) - min) / bucketSize).add(array.get(i));
 }
 for (int i = 0; i < bucketCount; i++) {
 if (bucketSize == 1) { // 如果带排序数组中有重复数字时 
 for (int j = 0; j < bucketArr.get(i).size(); j++)
 resultArr.add(bucketArr.get(i).get(j));
 } else {
 if (bucketCount == 1)
 bucketSize--;
 ArrayList<Integer> temp = BucketSort(bucketArr.get(i), bucketSize);
 for (int j = 0; j < temp.size(); j++)
 resultArr.add(temp.get(j));
 }
 }
 return resultArr;
 }
}

java实现12种排序算法

（2）控制台输出结果

java实现12种排序算法

十．堆排序及其实现

（1）java实现堆排序

堆排序是一种树形选择排序方法，它的特点是：在排序的过程中，将array[0，...，n-1]看成是一颗完全二叉树的顺序存储结构，利用完全二叉树中双亲节点和孩子结点之间的内在关系，在当前无序区中选择关键字最大（最小）的元素。

  1. 若array[0，...，n-1]表示一颗完全二叉树的顺序存储模式，则双亲节点指针和孩子结点指针之间的内在关系如下：

任意一节点指针 i：父节点：i==0 ? null : (i-1)/2

左孩子：2*i + 1

右孩子：2*i + 2

  1. 堆的定义：n个关键字序列array[0，...，n-1]，当且仅当满足下列要求：(0 <= i <= (n-1)/2)

① array[i] <= array[2*i + 1] 且 array[i] <= array[2*i + 2]；称为小根堆；

② array[i] >= array[2*i + 1] 且 array[i] >= array[2*i + 2]； 称为大根堆

  1. 建立大根堆：

n个节点的完全二叉树array[0，...，n-1]，最后一个节点n-1是第(n-1-1)/2个节点的孩子。对第(n-1-1)/2个节点为根的子树调整，使该子树称为堆

对于大根堆，调整方法为：若【根节点的关键字】小于【左右子女中关键字较大者】，则交换。

之后向前依次对各节点（(n-2)/2 - 1）~ 0为根的子树进行调整，看该节点值是否大于其左右子节点的值，若不是，将左右子节点中较大值与之交换，交换后可能会破坏下一级堆，于是继续采用上述方法构建下一级的堆，直到以该节点为根的子树构成堆为止。

反复利用上述调整堆的方法建堆，直到根节点。

  1. 堆排序：（大根堆）

① 将存放在array[0，...，n-1]中的n个元素建成初始堆；

② 将堆顶元素与堆底元素进行交换，则序列的最大值即已放到正确的位置；

③ 但此时堆被破坏，将堆顶元素向下调整使其继续保持大根堆的性质，再重复第②③步，直到堆中仅剩下一个元素为止。

空间复杂度:o(1)；

时间复杂度:建堆：o(n)，每次调整o(log n)，故最好、最坏、平均情况下：o(n*logn);

稳定性：不稳定

（2）java代码实现

java实现12种排序算法

package home;
public class HeapSort {
 public static void main(String[] args) {
 // TODO Auto-generated method stub
 HeapSort hs = new HeapSort();
 int[] array = { 87, 45, 78, 32, 17, 65, 53, 9, 122 };
 System.out.print("构建大根堆：");
 hs.toString(hs.buildMaxHeap(array));
 System.out.print("
" + "删除堆顶元素：");
 hs.toString(hs.deleteMax(array));
 System.out.print("
" + "插入元素63:");
 hs.toString(hs.insertData(array, 63));
 System.out.print("
" + "大根堆排序：");
 hs.toString(hs.heapSort(array));
 }
 // 删除堆顶元素操作
 private int[] deleteMax(int[] array) {
 // TODO Auto-generated method stub
 // 将堆的最后一个元素与堆顶元素交换，堆底元素值设为-99999
 array[0] = array[array.length - 1];
 array[array.length - 1] = -99999;
 // 对此时的根节点进行向下调整
 adjustDownToUp(array, 0, array.length);
 return array;
 }
 // 将元素array[k]自下往上逐步调整树形结构
 private void adjustDownToUp(int[] array, int k, int length) {
 // TODO Auto-generated method stub
 int temp = array[k];
 for (int i = 2 * k + 1; i < length - 1; i = 2 * i + 1) { // i为初始化为节点k的左孩子，沿节点较大的子节点向下调整
 if (i < length && array[i] < array[i + 1]) { // 取节点较大的子节点的下标
 i++; // 如果节点的右孩子>左孩子，则取右孩子节点的下标
 }
 if (temp >= array[i]) { // 根节点 >=左右子女中关键字较大者，调整结束
 break;
 } else { // 根节点 <左右子女中关键字较大者
 array[k] = array[i]; // 将左右子结点中较大值array[i]调整到双亲节点上
 k = i; // 【关键】修改k值，以便继续向下调整
 }
 }
 array[k] = temp; // 被调整的结点的值放人最终位置
 }
 private void toString(int[] array) {
 // TODO Auto-generated method stub
 for (int i : array) {
 System.out.print(i + " ");
 }
 }
 // 构建大根堆：将array看成完全二叉树的顺序存储结构
 private int[] buildMaxHeap(int[] array) {
 // TODO Auto-generated method stub
 // 从最后一个节点array.length-1的父节点（array.length-1-1）/2开始，直到根节点0，反复调整堆
 for (int i = (array.length - 2) / 2; i >= 0; i--) {
 adjustDownToUp(array, i, array.length);
 }
 return array;
 }
 // 插入操作:向大根堆array中插入数据data
 public int[] insertData(int[] array, int data) {
 // TODO Auto-generated method stub
 array[array.length - 1] = data; // 将新节点放在堆的末端
 int k = array.length - 1; // 需要调整的节点
 int parent = (k - 1) / 2; // 双亲节点
 while (parent >= 0 && data > array[parent]) {
 array[k] = array[parent]; // 双亲节点下调
 k = parent;
 if (parent != 0) {
 parent = (parent - 1) / 2; // 继续向上比较
 } else { // 根节点已调整完毕，跳出循环
 break;
 }
 }
 array[k] = data; // 将插入的结点放到正确的位置
 return array;
 }
 // 堆排序
 public int[] heapSort(int[] array) {
 // TODO Auto-generated method stub
 array = buildMaxHeap(array); // 初始建堆，array[0]为第一趟值最大的元素
 for (int i = array.length - 1; i > 1; i--) {
 int temp = array[0]; // 将堆顶元素和堆低元素交换，即得到当前最大元素正确的排序位置
 array[0] = array[i];
 array[i] = temp;
 adjustDownToUp(array, 0, i); // 整理，将剩余的元素整理成堆
 }
 return array;
 }
}

java实现12种排序算法

（3）控制台输出结果

java实现12种排序算法

十一.二叉树排序及有序集合

（1）代码实现

BinaryTree类：

java实现12种排序算法

package home;
public class BinaryTree {
 class Node { // 声明一个节点类
 private Comparable data; // 节点的数据类型为Comparable
 private Node left; // 保存左子树
 private Node right; // 保存右子树
 public Node(Comparable data) { // 构造函数
 this.data = data;
 }
 public void addNode(Node newNode) {
 // 确定是放在左子树还是右子树
 if (newNode.data.compareTo(this.data) < 0) { // 新节点值小于当前节点
 if (this.left == null) {
 this.left = newNode; // 左子树为空的话，新节点设为左子树
 } else {
 this.left.addNode(newNode); // 否则继续向下判断
 }
 } else { // 新节点的值大于或等于当前节点
 if (this.right == null) {
 this.right = newNode;
 } else {
 this.right.addNode(newNode);
 }
 }
 }
 public void printNode() { // 采用中序遍历
 if (this.left != null) { // 如果不为空先输出左子树
 this.left.printNode();
 }
 System.out.print(this.data + "	"); // 输出当前根节点
 if (this.right != null) { // 输出右子树
 this.right.printNode();
 }
 }
 }
 private Node root; // 表示根元素
 public void add(Comparable data) { // 向二叉树中插入元素
 Node newNode = new Node(data);
 if (root == null) { // 没有根节点
 root = newNode;
 } else {
 root.addNode(newNode); // 判断放在左子树还是右子树
 }
 }
 public void print() {
 root.printNode(); // 根据根节点输出
 }
}
BinaryTreeSort类：
package home;
public class BinaryTreeSort {
 public static void main(String[] args) {
 // TODO Auto-generated method stub
 BinaryTree bt = new BinaryTree();
 bt.add(3);
 bt.add(5);
 bt.add(4);
 bt.add(8);
 bt.add(7);
 bt.add(8);
 bt.add(1);
 bt.print();
 }
}

java实现12种排序算法

（2）控制台输出结果

java实现12种排序算法

十二.利用集合的4种排序排序方式

（1）代码实现

java实现12种排序算法

package home;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.IntSummaryStatistics;
import java.util.Iterator;
import java.util.List;
import java.util.TreeSet;
public class Test {
 public static void main(String[] args) {
 // TODO Auto-generated method stub
 int[] b = { 1, 2, 4, 3, 6, 9, 7, 11, 13, 15, 
 18, 19, 23, 34, 56, 1000, 23, 78, 890, 908 };
 
 System.out.println("sort1()结果显示：");
 Sort1(b);
 huanhang();
 
 System.out.println("sort2()结果显示：");
 Sort2(b);
 huanhang();
 
 System.out.println("sort3()结果显示：");
 Sort3(b);
 huanhang();
 
 System.out.println("sort4()结果显示：");
 sort4(b);
 huanhang();
 }
 //换两次行
 private static void huanhang() {
 // TODO Auto-generated method stub
 for(int i=0;i<=2;i++){
 System.out.println();
 }
 }
 private static void sort4(int[] b) {
 // TODO Auto-generated method stub
 List<Integer> lists = new ArrayList<Integer>();
 for (int i = 0; i < b.length; i++) {
 lists.add(b[i]);
 }
 // 排序，直接调用sort方法排序，排序方式是自然排序，即升序排序
 System.out.println("利用collections.sort()方法给list排序（默认为升序）：");
 Collections.sort(lists);
 
 // 遍历
 for(int i:lists){
 System.out.print(i+" ");
 } 
 System.out.println();
 System.out.println("利用collections.sort()方法给list降序排序"
 + "（先升序后用collections.reverse()反转）：");
 System.out.print("=============");
 System.out.println("java8使用lamda表达式(forEach方法)对集合进行遍历:");
 Collections.reverse(lists);
 
 //java8使用lamda表达式(forEach方法)对集合进行遍历
 lists.forEach(obj -> System.out.print(obj+" "));
 
 //java8使用lamda表达式Iterator的forEachRemaining方法)对集合进行遍历
 System.out.println("");
 System.out.print("=============");
 System.out.println("java8使用lamda表达式Iterator的forEachRemaining方法)"
 + "对集合进行遍历:");
 Iterator<Integer> it =lists.iterator();
 it.forEachRemaining(obj->System.out.print(obj+" "));
 }
 
 private static void Sort3(int[] b) {
 // TODO Auto-generated method stub
 // int数组转化为Integer数组
 int n = b.length;
 Integer[] iarr = new Integer[n];
 for (int i = 0; i < n; i++) {
 iarr[i] = new Integer(b[i]);
 }
 List<Integer> resultList = new ArrayList<>(iarr.length);
 Collections.addAll(resultList, iarr);
 
 System.out.println("利用collections给list排序：");
 for (int i : resultList) {
 System.out.print(i + " ");
 }
 }
 private static void Sort2(int[] b) {
 // TODO Auto-generated method stub
 @SuppressWarnings("unused")
 TreeSet<Integer> ts = new <Integer>TreeSet<Integer>();
 for (int i = 0; i < b.length; i++) {
 ts.add(b[i]);
 }
 System.out.println("利用TreeSet方集合排序（会去掉重复的元素）:");
 Iterator<Integer> it = ts.iterator();
 while (it.hasNext()) {
 System.out.print(it.next() + " ");
 }
 }
 private static void Sort1(int[] b) {
 // TODO Auto-generated method stub
 Arrays.sort(b);
 System.out.println("利用Arrays.sort()方法排序:");
 Arrays.stream(b).forEach(item -> {
 System.out.print(item + " ");
 });
 System.out.println();
 }
}

java实现12种排序算法

（2）控制台输出结果

java实现12种排序算法

作者：stringer123

原文：https://www.cnblogs.com/cuilongfei/p/10226750.html

排序算法 冒泡排序

yimixgg

yimixgg

0 关注 0 粉丝 0 动态

关注 关注

相关推荐

面试刷题必看！Python中的5大排序算法及其实现代码

排序是每个 IT 工程师和开发人员必备的知识技能。不仅要通过编程面试，而且要了解算法本身。不同的排序算法很好地展示了算法设计如何对程序的复杂性、速度和效率产生如此大的影响。让我们来看看排名前5，也是最常见，面试中经常被问到的排序算法，看看如何用Pytho

hang0 2020-08-16

Java数据结构与算法之冒泡排序、选择排序

它重复地走访过要排序的元素列，依次比较两个相邻的元素，如果顺序错误就把他们交换过来。走访元素的工作是重复地进行直到没有相邻元素需要交换，也就是说该元素列已经排序完成。从而减少不必要的比较。如果我们发现在某趟排序中，没有发生一次交换，可以提前结束冒泡排序。

风吹夏天 2020-07-07

JavaScript-数组排序（冒泡排序）

例如，我们可以将数组 [5, 4, 3, 2, 1]中的元素按照从小到大的顺序排序，输出： 1，2，3，4，5

baike 2020-06-27

【算法与数据结构】－－经典排序算法Python实现

return self.arr,count # 如果flag为false,说明此次排序没有任何交换，即已经排好顺序。for i in range: # 总共需要排序的次数为len-1. while insertindex >= 0 and ins

小海 2020-06-25

排序—插入排序

许久没有写点东西了，答辩之后人也变得松懈。今天看到简书又有人点赞之前记录的冒泡排序，点进去一看，居然有4w+的阅读量，心生疑问，咋会有这么高的阅读量，打开百度搜索冒泡排序，结果第3条就是我的。点开认真看了看，其实写得不好，还改了两个错别字(狗头)，这个阅读

清溪算法君老号 2020-06-06

三、排序之冒泡、插入、选择

时间复杂度反应的是数据规模 n 很大的时候的一个增长趋势，所以它表示的时候会忽略系数、常数、低阶。冒泡、插入、选择都是基于比较的排序算法。基于比较的排序算法的执行过程，会涉及两种操作，一种是元素比较大小，另一种是元素交换或移动。所以，如果我们在分析排序算法

wonner 2020-06-03

排序算法(冒泡排序、选择排序、插入排序、快速排序、归并排序）

　　是一种简单的排序算法。遍历数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最

清溪算法君老号 2020-06-01

Facebook借助人工智能对内容审核排序

据外媒，Facebook目前加大了对机器学习算法的应用，根据内容的权重，通过AI进行审核排序，同时设定了传播度、敏感度、违规严重程度这三大参考原则，但目前Facebook未透露具体的权重规则，总体上一旦过滤器遇到被标记可能违反平台政策、或被用户投诉的内容时

randy0 2020-11-17

排序算法之选择排序

首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。重复第二步，直到所有元素均排序完毕。

lixiaotao 2020-10-07

为什么排序的复杂度为O(N log N)

基本上所有正而八经的算法教材都会解释像快速排序quicksort和堆排序heapsort这样的排序算法有多快，但并不需要复杂的数学就能证明你可以逐渐趋近的速度有多快。大多数计算机专业的科学家使用大写字母 O 标记来指代“趋近，直到到达一个常数比例因子”，这

美丽的泡沫 2020-09-08

这两个问题都不清楚，还说会「归并排序」？

归并排序的迭代实现方式;实现一个原地归并排序;归并排序的迭代实现在正式看代码前，希望你心中清楚归并排序的递归实现方式，不熟悉也无妨，看这篇文章 图解「归并排序」算法(修订版) 文章。分的策略和递归的方式有别，依旧符合归并排序的思想;

nongfusanquan0 2020-08-18

LeetCode——合并K个排序链表

* Definition for singly-linked list.* int val;* ListNode *next;* };ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {

earthhouge 2020-08-15

LeetCode 数组：75. 颜色分类（计数排序 荷兰国旗问题）

题目也提示了计数排序的方法。当输入的元素是 n 个 0到 k 之间的整数时，时间复杂度是O(n+k)，空间复杂度也是O(n+k). 题目后来的要求是常数空间复杂度O1空间复杂度，一趟扫描On，肯定是在计数排序上有所发展。正确的方法是交换，p0指的是0区段的

算法改变人生 2020-07-28

归并排序

归并排序介绍:归并排序是利用归并的思想实现的排序方法，该算法采用经典的分治策略。

horizonheart 2020-07-19

排序算法

常见的内部排序：插入排序、交换排序、选择排序、归并排序、基数排序外排：归并排序、将第一待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。仅增量因子为 1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。

troysps 2020-07-19

看动画学算法之:排序-归并排序

归并排序简称Merge sort是一种递归思想的排序算法。这个算法的思路就是将要排序的数组分成很多小的部分，直到这些小的部分都是已排序的数组为止。接着将这些大一点的合并过的数组再继续合并，直到排序完整个数组为止。假如我们有一个数组：29,10,14,37,

Broadview 2020-07-19

排序算法整理

主要记快排和归并。快速排序的基本思想：通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。从数列中挑出一个元素，称为 “基准”；重新排序数列，所有元素比基准值小的摆

chenfei0 2020-07-18

排序算法

它的工作原理是：它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。希尔排序也成递减

yangjingdong00 2020-07-05

归并排序（merge_sort）

就是递归到最底部，然后对小部分排序，归并为大部分。int k = 0, i = l, j = mid+1;第二个参数是一个指向第 n 个元素的迭代器。如果这个范围内的元素是完全有序的，nth_dement() 的执行会导致第 n 个元素被放置在适当的位置。

数据与算法之美 2020-07-05

算法学习（二）选择排序

　　上一篇学习了冒泡排序，还是比较简单的一种排序，这一篇学习一下选择排序，也是基础排序的其中一种，手写一遍，加上自己的注释，理解以后写图例，其实算法也不是很高深的东西，记录一下~~//2、设置min变量，用于存放较小元素的数组下标，这样当前批次比较完毕时，

shawsun 2020-07-04
yimixgg

yimixgg

W3CSchool教程
HTML 教程
CSS 教程
Bootstrap 教程
Javascript 教程
jQuery 教程
后端教程
C 教程
Java 教程
PHP 教程
Python 教程
Go 教程
移动开发
Android 教程
Swift 教程
Kotlin 教程
jQuery Mobile 教程
ionic 教程
关于我们
新闻动态
联系方式
招聘英才
安科实验室
帮助与反馈

安科网(Ancii)，中国第一极客网

Copyright © 2013 - 2019 Ancii.com

京ICP备18063983号 京公网安备11010802014868号