数据结构与算法-排序算法

排序也称之为排序算法（Sort Algorithm）,是讲一组数据以指定的顺序进行排列的过程。 排序分类

 

 算法时间效率

基数排序 基数排序（radix sort）属于“分配式排序”（distribution sort），又称“桶子法”（bucket sort）或bin sort，顾名思义，它是透过键值的部份资讯，将要排序的元素分配至某些“桶”中，藉以达到排序作用， 基数排序法是属于稳定性的排序。 讲所有的待比较数值统一设置为同样的数位长度，位数比较短的数前面补零，然后从最地位开始依次进行一次排序，这样从最低位排序一直到最高位排序完成以后，数列就变成一个有序序列。 冒泡排序

冒泡排序的思想是通过对待排序序列从前往后依次比较相邻元素值，若发现逆序则交换，使值较大的元素从前逐步移向后面，就想水中气泡。 特点： 1、 需要循环array.length-1次 外层循环 2、 每次排序的次数逐步递减 3、 也可能存在本次排序没有发生变化

package com.mei.sort;


import java.util.Arrays;
//冒泡排序
public class BubblingSort {
    public static void main(String[] args) {
        int[] arrays=new int[]{4,5,6,3,2,1};
        
        for (int i = 0; i arrays[j+1]) {
                    int temp = 0;//类似于空桶
                    temp = arrays[j];
                    arrays[j] = arrays[j + 1];
                    arrays[j + 1] = temp;
                }
            }
        }

        System.out.println(Arrays.toString(arrays));
    }

}

快速排序 快速排序是对冒泡排序的一种改进。通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另一部分所有的数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列

package com.mei.sort;

import java.util.Arrays;
//快速排序
public class QuickSort {
    public static void main(String[] args) {
        int[] arrays=new int[]{2,9,4,7,3,3,6,5};
        sort(arrays,0,arrays.length-1);

        System.out.println(Arrays.toString(arrays));
    }
    public static void sort(int[] arrays,int left,int right){
        int l=left;
        int r=right;
        int pivot=arrays[(left+right)/2];
        int temp=0;
        while (lpivot){
                r--;
            }
            if (l>=r){
                break;
            }
            temp=arrays[l];
            arrays[l]=arrays[r];
            arrays[r]=temp;

            
            if (arrays[l]==pivot){
                r--;
            }
            if (arrays[r]==pivot){
                l++;
            }
            
            if(r==l){
                l++;
                r--;
            }
            if (leftl){
                sort(arrays,l,right);
            }
        }
    }
}

插入排序 插入排序属于内部排序，是对于排序的元素以插入的方式寻找该元素的适当位置，已达到排序的目的

 

package com.mei.sort;

import java.util.Arrays;
//插入排序后面的一个元素和前面的比较
public class InsertSort {
    public static void main(String[] args) {
        int[] arrays=new int[]{2,5,6,3,4,7,1,8};
        for (int i = 0; i =1;j--){
                if (arrays[j]

 选择排序 第一次从待排序数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后再从剩余的未排序元素中寻找到最小（大）元素，然后放到已排序的序列的末尾。

插入排序是后边的一个元素与前边的比较，选择排序未排序的的无序数组找到最大值或者最小值，排到排好的尾端

package com.mei.sort;

import java.util.Arrays;
//选择排序
//无序的序列找到最大值或者最小值
//随着有序的序列变长，无序序列在缩短
public class SelectSort {
    public static void main(String[] args) {
        int[] arrays=new int[]{3,2,4,5,6,8,7,1};
        for (int i = 0; i i; j--) {//每一轮找最大或者最小值
                if(arrays[j]

希尔排序 希尔排序是插入排序的一种又称“缩小增量排序”，是插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。

 

package com.mei.sort;

import java.util.Arrays;

public class ShellSort {
    public static void main(String[] args) {
        int[] array = new int[]{1,5,9,7,2,6,0,3,8,4};
        
        for (int gap=array.length/2;gap>0;gap/=2){
            for (int i=gap;i=0;j-=gap){//间隔为五的时候
                    if (array[j]>array[j+gap]){
                        int temp=0;
                        temp=array[j];
                        array[j]=array[j+gap];
                        array[j+gap]=temp;
                    }
                }
            }
        }
        System.out.println(Arrays.toString(array));
    }

}