经典的十种排序算法（java实现）

经典的十种排序，1~7属于比较类型的排序。8~10属于非比较类型的排序。（以下所有排序算法都是按照升序排序） 1.冒泡排序 （BubbleSort）

时间复杂度O（n^2 ） 采用二层for循环；空间复杂度O（1）  稳定性：稳定

 思想:

   从数组中的第一个元素跟其下一个元素进行比较，若前面的比后面大，则进行交换。然后该最大值又跟他的下一个元素比较，若若前面的比后面大，则进行交换。直到比较到数组的倒数第二个元素，则自然找到这个数组中的最大元素。此时数组长度-1。再次重复上面的操，就可以将数组排好序。

步骤：          外层for：控制需要多少次循环才能将数组排好序          内层for：控制需要两两比较的次数 代码部分：

  public static void main(String[] args) {
        int arr[] = new int[10];//创建一个长度为10的数组
        //随机产生10个数放入数组中
        Random random = new Random();
        for (int i = 0; i < arr.length; i++) {
            arr[i] = random.nextInt(100);//范围：1~100
        }
        System.out.println("原数组="+Arrays.toString(arr));
        bubbleSort(arr);
    }

    public static void bubbleSort(int[] a) {
        //外层控制循环的次数
        for (int i = 0; i < a.length-1; i++) {
            //内层控制比较的次数
            for (int j =0; j a[j+1]){
                    int temp=a[j];
                    a[j]=a[j+1];
                    a[j+1]=temp;
                }
            }
        }
        System.out.println("排序后数组="+Arrays.toString(a));
    }

2.选择排序 （SelectSort）

时间复杂度O（n^2 ） 采用二层for循环；空间复杂度O（1）  稳定性：不稳定

 思想:

        将数组第一个位置假设为最小（最大值），因为我们这里都是升序排序，因此将数组第一个索引位置，当成最小值。最小值跟后面的所有数字进行比较，遇到比最小的小的，就把索引当前索引位置赋给它。然后如此循环下去，每次都能找到剩下数字中最小的值。

步骤：          外层for：选择出来一个值          内层for：选择出来的值的下个索引          然后进行比较，遇到小的交换 代码部分：

 public static void main(String[] args) {
        int arr[] = new int[10];//创建一个长度为10的数组
        //随机产生10个数放入数组中
        Random random = new Random();
        for (int i = 0; i < arr.length; i++) {
            arr[i] = random.nextInt(100);//范围：1~100
        }
        System.out.println("原数组=" + Arrays.toString(arr));
        selectSort(arr);
        System.out.println("排序后的数组=" + Arrays.toString(arr));
    }
    public static void selectSort(int[]a){
        //循环遍历数组
        for (int i = 0; i a[j]?j:minPos;//遇到比假设的最小值还小的数值，将这个索引赋值给他
            }
            //经过上面for，我们每次都能找到一个最小值，因此需要进行交换
            int temp=a[i];
            a[i]=a[minPos];
            a[minPos]=temp;
        }
    }

3.插入排序 （InsertSort）

时间复杂度O（n^2 ） 采用二层for循环；空间复杂度O（1）  稳定性：稳定

 思想:

          也相当于找最小值，只不过呢，插入排序第一次的时候，将数组的一个位置留着，它跟后面的比较（升序就找最小值），如果是后面的值比前面的值小，则进行交换。现在这前面的二个数就有序。然后第三个值跟第二个值比较，如果还是小的话，进行交换，然后在跟最前面的比较。

例子：就相当于你打牌，先抽的牌已经有顺序了，你从下面在拿上来了一张牌，需要重新排好顺序，你得从有顺序的最末尾比较后，挨个进行交换比较，将你拿上的牌插入进去后，数组又有顺序。

步骤：          外层for：控制需要多少次循环才能将数组排好序          内层for：控制需要两两比较的次数 代码部分：

 public static void main(String[] args) {
    int arr[] = new int[10];//创建一个长度为10的数组
    //随机产生10个数放入数组中
    Random random = new Random();
    for (int i = 0; i < arr.length; i++) {
        arr[i] = random.nextInt(100);//范围：1~100
    }
    System.out.println("原数组=" + Arrays.toString(arr));
        insertSort(arr);
    System.out.println("排序后的数组=" + Arrays.toString(arr));
    }
    public static void insertSort(int []a){
        //外层循环(第一次，手上有一张牌，不需要排序)
        for (int i = 1; i 0 ; j--) {//抽上来的牌，要跟你开始的牌进行比较
                if (a[j]

4.希尔排序 （ShellSort）

     时间复杂度O（n^1.3 ） 采用二层for循环；空间复杂度O（1）  稳定性：不稳定

 思想:

          希尔排序是一种特殊的插入排序，他以某种间隔抽取数组排序。经常用Kunth（唐纳德·克努特）间隔抽取数组。对每个用Kunth间隔分出来的数组进行排序，然后直到分割到单位元素时，进行最后一次排序，就可以将数组排好序。

步骤：          外层for：控制需要多少次循环才能将数组排好序          内层for：控制需要两两比较的次数 代码部分：

public static void main(String[] args) {
        int arr[] = new int[10];//创建一个长度为10的数组
        //随机产生10个数放入数组中
        Random random = new Random();
        for (int i = 0; i < arr.length; i++) {
            arr[i] = random.nextInt(100);//范围：1~100
        }
        System.out.println("原数组=" + Arrays.toString(arr));
        shellSort(arr);
        System.out.println("排序后的数组=" + Arrays.toString(arr));
    }
    public static void shellSort(int []a){
        //根据Kunth（唐纳德·克努特）计算出间隔
        int h=1;
        while (h <= a.length / 3) {
            h = 3 * h + 1;
        }
        //while循环结束后，就可以得到数组的间隔长度
        for (int gap = h; gap >0; gap=(gap-1)/3) {
            //根据间隔找到各个组
            for (int i = gap; i =0 ; j-=gap) {
                    //当前元素和加上间隔长度的数进行比较
                    if (a[j]>a[j+gap]){//控制升序排列
                        int temp=a[j];
                        a[j]=a[j+gap];
                        a[j+gap]=temp;
                    }
                }
            }
        }
    }

5.快速排序 （QuickSort）

    时间复杂度O（nlogn ） ；空间复杂度O（logn）  稳定性：不稳定

 思想:

         找到一个基准数，将小于基准数的放在左边，大于基准数的放在右边，当左边遇到一个比基准数大的，右边遇到基准数小的数，此时进行交换。当符合左边的数全部小于基准数，右边的数全部大于基准数，在分别对左右二边在分，进行上面的重复操作。

步骤：        先找到基准数（这里以中间的索引位置的数）        当从数组的最左边依次寻找，从数组的最右边依次寻找，存在左边的索引大于右边的索引时，则跳出循环。        反复对左边右边进行分解，直到分解到单位元素排序结束，此时排序完成。 代码部分：

 public static void main(String[] args) {
        int arr[] = new int[10];//创建一个长度为10的数组
        //随机产生10个数放入数组中
        Random random = new Random();
        for (int i = 0; i < arr.length; i++) {
            arr[i] = random.nextInt(100);//范围：1~100
        }
        System.out.println("原数组=" + Arrays.toString(arr));
        quickSort(arr, 0, arr.length - 1);
        System.out.println("排序后的数组=" + Arrays.toString(arr));
    }

    public static void quickSort(int[] a, int left, int right) {
        int lo = left;//数组最左边索引
        int hi = right;//数组最右边索引
        int midValue= a[(left+right)/2];//基准数
        //开始按照比基准小的放左边，比基准数大的放在右边
        while (lomidValue){
                hi--;
            }
            //左边找到个比基本数大的，右边找个比基准数小的时，进行交换
            if (lo 
6.归并排序 （MergeSort） 
时间复杂度O（nlogn ） 先拆后合；空间复杂度O（1）  稳定性：稳定
 
思想： 
      先将数组分成二段（按照索引的mid），然后在看左边那段是否有序，如果没有在拆分（按照中间索引），如此循环下去，知道拆分成单一元素为止。从单一元素不断合并，最终合并成一个完整的数组。
 
步骤： 
        拆分：左边端有序列，右端有序列 
       合并：左右二边都有序的情况进行合并 
代码部分： 
public static void main(String[] args) {
        int arr[] = new int[10];//创建一个长度为10的数组
        //随机产生10个数放入数组中
        Random random = new Random();
        for (int i = 0; i < arr.length; i++) {
            arr[i] = random.nextInt(100);//范围：1~100
        }
        System.out.println("原数组=" + Arrays.toString(arr));
        mergeSort(arr,0,arr.length-1);
        System.out.println("排序后的数组=" + Arrays.toString(arr));
    }
    //拆+合
    public static void mergeSort(int a[],int left, int right){
       //求索引的中间值
        if (left 

 9.计数排序 （CountSort） 
时间复杂度O（n+k） 采用桶的思想；空间复杂度O（n+k）  稳定性：稳定  
 
思想： 
    创建一个一维数组长度为最大值+1用来记录数字出现的次数
 
步骤： 
          通过循环找到该数组中最大的数，在创建一个一维数组来记录数字出现的次数
 
在依次放入原数组。
 
代码部分： 
public static void main(String[] args) {
        int arr[] = new int[10];//创建一个长度为10的数组
        //随机产生10个数放入数组中
        Random random = new Random();
        for (int i = 0; i < arr.length; i++) {
            arr[i] = random.nextInt(100);//范围：1~100
        }
        System.out.println("原数组=" + Arrays.toString(arr));
        countSort(arr);
    }
    public static void countSort(int[]a){
        int max=a[0];//初始化最大值
        //找到数组中最大值
        for (int i = 1; i max?a[i]:max;
        }
        //创建一个一维数组来记录数组出现的次数
        int[] countBucket = new int[max + 1];
        for (int i = 0; i 
 
10.桶排序  （BucketSort） 
时间复杂度O（n+k） 采用桶的思想；空间复杂度O（n+k）  稳定性：稳定  
 
思想： 
       创建一个一维数组长度为最大值+1用来记录数字出现的次数
 
步骤： 
          通过循环找到该数组中最大的数，在创建一个一维数组来记录数字出现的次数
 
在依次放入原数组。
 
代码部分：
 
public static void main(String[] args) {
        int arr[] = new int[10];//创建一个长度为10的数组
        //随机产生10个数放入数组中
        Random random = new Random();
        for (int i = 0; i < arr.length; i++) {
            arr[i] = random.nextInt(100);//范围：1~100
        }
        System.out.println("原数组=" + Arrays.toString(arr));
        bucketSort(arr);
    }

    public static void bucketSort(int[] a) {
        int max = a[0];//初始化数组的最大值
        //找到数组中的最大值
        for (int i = 1; i < a.length; i++) {
            max = a[i] > max ? a[i] : max;
        }
        //桶的长度为max+1
        int[] bucket = new int[max + 1];
        for (int i = 0; i < a.length; i++) {
            bucket[a[i]]++;
        }
        //将桶中的数据放回原数组
        int index = 0;
        for (int i = 0; i < bucket.length; i++) {
            if (bucket[i]!=0){
                a[index++]=i;
            }
        }
        System.out.println("排序后的数组=" + Arrays.toString(a));
    }
 
                                         创作不易，还望收藏，点赞！