java十大经典排序

经过一段时间学习排序算法，对排序有了一定的了解，在此记录一下，作为以后的笔记，在这无动画演示，感兴趣可以自行百度，这里不敢保证自己说的都正确，欢迎各位大佬指正。（代码比较少注释说明，建议还是先理解好各个排序算法的逻辑，才更好理解此篇文章）
这里有参考到此文章：https://blog.csdn.net/meibenxiang/article/details/92796909

排序的相关介绍：
1.稳定：如果a原本在b前面，而a=b,排序之后a仍然在b的前面；
2.不稳定：如果a原本在b前面，而a=b,排序之后a有可能会出现在b的后面；
3.内排序：所有排序操作都在内存中完成；
4.外排序：由于数据太大，因此把数据放在磁盘中，而排序通过磁盘和内存的数5.据传输才能进行；
6. 时间复杂度：描述算法运行时间的函数，用大O符号表述；
7.空间复杂度：描述算法所需要的内存空间大小。

1.冒泡排序
它重复地走访过要排序的元素列，依次比较两个相邻的元素，如果顺序（如从大到小、首字母从Z到A）错误就把他们交换过来。走访元素的工作是重复地进行直到没有相邻元素需要交换，也就是说该元素列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端（升序或降序排列），就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样，故名“冒泡排序”。

public class MaoPao {
 public static void main(String[] args) {
  int arr[]= {6,2,4,9,8,1};
  System.out.print("排序前的数组：");
  for(int i=0;i<arr.length;i++) {
   System.out.print(arr[i]+" ");
  }
  System.out.println();
  for(int i=0;i<arr.length-1;i++) {
   for(int j=0;j<arr.length-1-i;j++) {
    if(arr[j]>arr[j+1]) {
     int tem=arr[j];
     arr[j]=arr[j+1];
     arr[j+1]=tem;
    }
   }
  }
  System.out.print("排序后的数组：");
  for(int i=0;i<arr.length;i++) {
   System.out.print(arr[i]+" ");
  }
 }
}

排序结果为：

冒泡排序最好的时间复杂度为O（n），最坏时间复杂度为O（n2）。
最差的空间复杂度就是开始元素逆序排序了，则空间复杂度为：O(n)；
最优的空间复杂度就是开始元素顺序已经排好了，则空间复杂度为：0；

`2.选择排序
选择排序（Selection sort）是一种简单直观的排序算法。它的工作原理是：第一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后再从剩余的未排序元素中寻找到最小（大）元素，然后放到已排序的序列的末尾。以此类推，直到全部待排序的数据元素的个数为零。选择排序是不稳定的排序方法。

public class SelectionSort {
 public static void main(String[] args) {
  int arr[]= {6,2,4,9,8,1};
  System.out.print("排序前的数组：");
  for(int i=0;i<arr.length;i++) {
   System.out.print(arr[i]+" ");
  }
  System.out.println();
  for(int i=0;i<arr.length-1;i++) {
   int min=i;
   for(int j=i+1;j<arr.length;j++) {
    if(arr[min]>arr[j]) {
     min=j;
    }
   }
   if(min!=i) {
    int tem=arr[i];
    arr[i]=arr[min];
    arr[min]=tem;
   }
  }
  System.out.print("排序后的数组：");
  for(int i=0;i<arr.length;i++) {
   System.out.print(arr[i]+" ");
  }
 }
}

排序结果为：

选择排序最好的时间复杂度为O（n），最坏时间复杂度为O（n2）。
空间复杂度是O(1)。

3.插入排序
插入排序（Insertion sort）是一种简单直观且稳定的排序算法。如果有一个已经有序的数据序列，要求在这个已经排好的数据序列中插入一个数，但要求插入后此数据序列仍然有序，这个时候就要用到一种新的排序方法——插入排序法,算法适用于少量数据的排序，时间复杂度O(n^2)。是稳定的排序方法。插入算法把要排序的数组分成两部分：第一部分包含了这个数组的所有元素，但将最后一个元素除外（让数组多一个空间才有插入的位置），而第二部分就只包含这一个元素（即待插入元素）。在第一部分排序完成后，再将这个最后元素插入到已排好序的第一部分中。
插入排序的基本思想是：每步将一个待排序的记录，按其关键码值的大小插入前面已经排序的文件中适当位置上，直到全部插入完为止。

public class InsertionSort {
 public static void main(String[] args) {
  int a[]= {6,2,4,9,8,1};
  int temp=0;  
  System.out.print("排序前的数组：");
  for(int i=0;i<a.length;i++) {
   System.out.print(a[i]+" ");
  }
  System.out.println();
     for(int i=1;i<a.length;i++){  
        int j=i-1;  
        temp=a[i];
        for(;j>=0&&temp<a[j];j--){
        a[j+1]=a[j]; 
        }  
        a[j+1]=temp;  
     }  
     System.out.print("排序后的数组：");
     for(int i=0;i<a.length;i++)  
        System.out.print(a[i]+" ");  
 }
}

排序结果为：

在最好的情况下（元素已经排好顺序），那么只需要循环 n-1 次就可以了，时间复杂度 O（n）；
在最差的情况下 （元素是逆序的）：要循环调整次数： [ n * (n-1) ] / 2 ，时间复杂度为 O（n ^ 2）；

4.快速排序
快速排序（Quicksort）是对冒泡排序的一种改进。 快速排序由C. A. R. Hoare在1962年提出。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

import java.util.*;
public class Quicksort {
 public static void main(String[] args) {
  int arr[]= {6,2,4,9,8,1};
  System.out.print("排序前的数组：");
  System.out.print(Arrays.toString(arr));
  sort(arr,0,arr.length-1);
  System.out.println();
  System.out.print("排序前的数组：");
  System.out.print(Arrays.toString(arr));
 }
public static void sort(int[] arr,int low,int hight) {
 if(low>=hight) {
  return;
 }
 int i=low;
 int j=hight;
 int key=arr[i];
 while(i<j) {
  while(arr[j]>=key&&i<j) {
   j--;
  }
   int tem;
   tem=arr[j];
   arr[j]=arr[i];
   arr[i]=tem;
  while(arr[i]<=key&&i<j) {
   i++;
  }
  tem=arr[i];
  arr[i]=arr[j];
  arr[j]=tem;
  sort(arr,low,i-1);
  sort(arr,i+1,hight);  
 }
}
}

排序结果为：

快速排序最优的情况下时间复杂度为：O( nlogn )；
快速排序最差的情况下时间复杂度为：O( n^2 )；
最优的情况下空间复杂度为：O(logn) ；每一次都平分数组的情况；
最差的情况下空间复杂度为：O( n ) ；退化为冒泡排序的情况。

5.希尔排序
希尔排序(Shell’s Sort)是插入排序的一种又称“缩小增量排序”（Diminishing Increment Sort），是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。该方法因D.L.Shell于1959年提出而得名。
希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。

import java.util.*;
public class ShellSort {
 public static void main(String[] args) {
  int arr[]= {6,2,4,9,8,1};
  System.out.print("排序前的数组：");
  for(int i=0;i<arr.length;i++) {
   System.out.print(arr[i]+" ");
  }
  System.out.println();
        System.out.print("排序后的数组：");
        shellSort(arr);      
        for(int i=0;i<arr.length;i++) {
   System.out.print(arr[i]+" ");
  }
 }
 public static String shellSort(int[] arr) {
     int current;
     int gap = arr.length / 2; //分组
     while(gap > 0) {
         for(int i=gap; i<arr.length; i++) {
             current = arr[i];
             int preIndex = i - gap;
             while(preIndex >= 0 && current < arr[preIndex]) {
                 arr[preIndex + gap] = arr[preIndex];
                 preIndex -= gap;
             }
             arr[preIndex + gap] = current;
         }
         gap /= 2;
     }        
     return Arrays.toString(arr);
 }
}

排序结果为：

时间复杂度：O(n log^2 n）)
空间复杂度：O(1)
稳定性：不稳定

6.堆排序
堆排序（英语：Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点

public class Heapsort {
 public static void main(String[] args) {
  int arr[]= {6,2,4,9,8,1};
  System.out.print("排序前的数组：");
  for(int i=0;i<arr.length;i++) {
   System.out.print(arr[i]+" ");
  }
  System.out.println();
  System.out.print("排序后的数组：");
  headSort(arr);
  for(int i=0;i<arr.length;i++) {
   System.out.print(arr[i]+" ");
  }
 }
 public static void headSort(int[] list) {
         for (int i = (list.length) / 2 - 1; i >= 0; i--) {
            headAdjust(list, list.length, i);
        }
        for (int i = list.length - 1; i >= 1; i--) {
            int temp = list[0];
            list[0] = list[i];
            list[i] = temp;
            headAdjust(list, i, 0);
        }
    }    
    private static void headAdjust(int[] list, int len, int i) {
        int k = i, temp = list[i], index = 2 * k + 1;
        while (index < len) {
            if (index + 1 < len) {
                if (list[index] < list[index + 1]) {
                    index = index + 1;
                }
            }
            if (list[index] > temp) {
                list[k] = list[index];
                k = index;
                index = 2 * k + 1;
            } else {
                break;
            }
        }
        list[k] = temp;
    }
}

排序结果为：

堆排序的时间复杂度为O(n log n)；
空间复杂度为：O(1)

7.归并排序
归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。归并排序是一种稳定的排序方法。
这是学习此篇文章：
https://blog.csdn.net/qq_36442947/article/details/81612870

public class MergeSort {
 public static void main(String[] args) {
  int arr[]= {6,2,4,9,8,1};
  System.out.print("排序前的数组：");
  for(int i=0;i<arr.length;i++) {
   System.out.print(arr[i]+" ");
  }
  System.out.println();
  mergeSort(arr, 0, arr.length-1);
   System.out.print("排序后的数组：");   
         for(int i=0;i<arr.length;i++) {
    System.out.print(arr[i]+" ");
   }
 }
 //两路归并算法，两个排好序的子序列合并为一个子序列
    public static void merge(int []arr,int left,int mid,int right){
        int []tmp=new int[arr.length];//辅助数组
        int p1=left,p2=mid+1,k=left;//p1、p2是检测指针，k是存放指针
        while(p1<=mid && p2<=right){
            if(arr[p1]<=arr[p2])
                tmp[k++]=arr[p1++];
            else
                tmp[k++]=arr[p2++];
        }
        while(p1<=mid) tmp[k++]=arr[p1++];//如果第一个序列未检测完，直接将后面所有元素加到合并的序列中
        while(p2<=right) tmp[k++]=arr[p2++];//同上
        //复制回原素组
        for (int i = left; i <=right; i++) 
            arr[i]=tmp[i];
    }
    public static void mergeSort(int [] arr,int start,int end){
        if(start<end){//当子序列中只有一个元素时结束递归
            int mid=(start+end)/2;//划分子序列
            mergeSort(arr, start, mid);//对左侧子序列进行递归排序
            mergeSort(arr, mid+1, end);//对右侧子序列进行递归排序
            merge(arr, start, mid, end);//合并
        }
    }
}

排序结果为：

归并排序的时间复杂度为n log n；
空间复杂度为: O(n)

8.桶排序
桶排序 (Bucket sort)或所谓的箱排序，是一个排序算法，工作的原理是将数组分到有限数量的桶子里。每个桶子再个别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序）。桶排序是鸽巢排序的一种归纳结果。当要被排序的数组内的数值是均匀分配的时候，桶排序使用线性时间（Θ（n））。但桶排序并不是 比较排序，他不受到 O(n log n) 下限的影响。

public class BucketSort {
 private int[] bucket;
 private int[] array;
 // size是一个范围
 public BucketSort(int[] array) {
  this.array = array;
  int max = array[0];
  int min = array[0];
  for(int i=0; i<array.length; ++i){
   if(array[i]>max){
    max = array[i];
   }
   if(array[i]<min){
    min = array[i];
   }
  }
  bucket = new int[max-min+1]; //算出需要开辟多少个空间  
 }
 public void sort() {
  for (int i = 0; i < array.length; ++i) {
   bucket[array[i]]++;
  }
 }
 // 遍历桶，并得到每个桶中数n，并输出n次该桶下标
 public void print() {
  for (int i = 0; i < bucket.length; i++){
   for (int j = 0; j < bucket[i]; j++){
    System.out.print(i+" ");
   }
  } 
 } 
 public static void main(String[] args) {
   int[] array = new int[]{3,1,5,9,6,5,0};
   System.out.print("排序前的数组：");
   for(int i=0;i<array.length;i++) {
    System.out.print(array[i]+" ");
   }
   System.out.println();
   System.out.print("排序后的数组：");
       BucketSort order = new BucketSort(array); 
       order.sort();
       order.print();
 }
}

排序结果为：

桶排序时间复杂度最坏: O(n^2)
桶排序时间复杂度最好: O(n+k)
桶排序空间复杂度：O（n+k）

9.计数排序
计数排序的基本思想是对于给定的输入序列中的每一个元素x，确定该序列中值小于x的元素的个数（此处并非比较各元素的大小，而是通过对元素值的计数和计数值的累加来确定）。一旦有了这个信息，就可以将x直接存放到最终的输出序列的正确位置上。例如，如果输入序列中只有17个元素的值小于x的值，则x可以直接存放在输出序列的第18个位置上。当然，如果有多个元素具有相同的值时，我们不能将这些元素放在输出序列的同一个位置上，因此，上述方案还要作适当的修改。

public class CountingSort {
 public static void main(String[] args) {
  int arr[]= {6,2,4,9,8,1};
  System.out.print("排序前的数组：");
  for(int i=0;i<arr.length;i++) {
   System.out.print(arr[i]+" ");
  }
  System.out.println();
  System.out.print("排序后的数组：");
  sortCount(arr, 1, 10);
  for(int i=0;i<arr.length;i++) {
   System.out.print(arr[i]+" ");
  }
 }
  public static void sortCount(int[] arr, int m, int n) {
         int len = arr.length;
         int[] tem = new int[n - m + 1];
         for(int i = 0; i < len; i++) {
             tem[arr[i] - m] += 1;
         }
         for(int i = 0, index = 0; i < tem.length; i++) {
             int item = tem[i];
             while(item-- != 0) {
                 arr[index++] = i + m;
             }
         }
     }
}

排序结果为：

计数排序最优的情况下时间复杂度为：O(n+k )；
计数排序最差的情况下时间复杂度为：O(n+k )；
最优的情况下空间复杂度为：O(k) ；

10.基数排序
基数排序（radix sort）属于“分配式排序”（distribution sort），又称“桶子法”（bucket sort）或bin sort，顾名思义，它是透过键值的部份资讯，将要排序的元素分配至某些“桶”中，藉以达到排序的作用，基数排序法是属于稳定性的排序，其时间复杂度为O (nlog®m)，其中r为所采取的基数，而m为堆数，在某些时候，基数排序法的效率高于其它的稳定性排序法。
学习此文章所得：https://www.cnblogs.com/developerY/p/3172379.html

public class RadixSort {
 public static void main(String[] args) {
  int arr[]= {6,2,4,9,8,1};
  System.out.print("排序前的数组：");
  for(int i=0;i<arr.length;i++) {
   System.out.print(arr[i]+" ");
  }
  System.out.println();
  System.out.print("排序后的数组：");
   radixSort(arr, 100);
   for(int i=0;i<arr.length;i++) {
    System.out.print(arr[i]+" ");
   }
 }
 private static void radixSort(int[] array,int d)
 {
     int n=1;//代表位数对应的数：1,10,100...
     int k=0;//保存每一位排序后的结果用于下一位的排序输入
     int length=array.length;
     int[][] bucket=new int[10][length];//排序桶用于保存每次排序后的结果，这一位上排序结果相同的数字放在同一个桶里
     int[] order=new int[length];//用于保存每个桶里有多少个数字
     while(n<d)
     {
         for(int num:array) //将数组array里的每个数字放在相应的桶里
         {
             int digit=(num/n)%6;
             bucket[digit][order[digit]]=num;
             order[digit]++;
         }
         for(int i=0;i<length;i++)//将前一个循环生成的桶里的数据覆盖到原数组中用于保存这一位的排序结果
         {
             if(order[i]!=0)//这个桶里有数据，从上到下遍历这个桶并将数据保存到原数组中
             {
                 for(int j=0;j<order[i];j++)
                 {
                     array[k]=bucket[i][j];
                     k++;
                 }
             }
             order[i]=0;//将桶里计数器置0，用于下一次位排序
         }
         n*=6;
         k=0;//将k置0，用于下一轮保存位排序结果
     }     
 }
}

排序结果为：

基数排序时间复杂度为O（n*k），其中n为数据个数，k为数据位数。
基数排序空间复杂度为O（n+k）

整理完成，若有不正确的地方，欢迎各位指出！

最后

以上就是高贵嚓茶为你收集整理的java十大经典排序的全部内容，希望文章能够帮你解决java十大经典排序所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。