博客

十大经典排序算法

  • Post author:
  • Post category:其他




十大经典排序算法（Java）



0.0算法概述



0.1算法分类

十种常见的排序算法可分为以下两大类：

  1. 比较类排序：通过比较来决定元素间的相对位置，由于其时间复杂度不能突破O(nlogn)，因此也称为非线性时间比较类排序。
  2. 非比较类排序：不通过比较来决定元素间的相对位置，它可以突破基于比较排序的时间下限，以线性时间运行，因此也称为线性时间非比较类排序。

排序算法的分类



0.2算法复杂度

算法复杂度



0.3相关概念


  • 时间复杂度：

    从序列的初始状态到经过排序算法的变换移位等操作变到最终排序好的结果状态的过程所花费的时间度量。

  • 空间复杂度：

    就是从序列的初始状态经过排序移位变换的过程一直到最终的状态所花费的空间开销。

  • 稳定性：

    待排序序列中相等的数据经排序算法执行后，其相对位置始终不变则称该算法稳定。反之，该排序算法不稳定。



1.0冒泡排序（Bubble Sort）



1.1基本思想

重复的走访要排序的元素序列，依次比较两个相邻元素，顺序错误则交换位置。走访的工作重复进行，直到没有相邻元素需要交换，即排序完成。每一轮比较结束，最小(最大)的元素会经由交换慢慢的“浮”到数列的顶端，故称冒泡。



1.2动图演示

冒泡排序动图



1.3算法描述

  1. 外循环，要进行


    len-1


    轮比较，使得


    len-1


    个数据从无序区


    冒泡


    到有序区。

  2. 内循环，相邻元素间比较，顺序错误则交换位置。



1.4代码实现

public static void bubbleSort(int arr[]) {
    int len = arr.length;   //数组元素的个数

    //需要 len-1 轮的冒泡
    for(int i=0;i<len-1;i++) {
        //每轮使得一个气泡冒出水面到有序区区
        for(int j=0;j<len-i-1;j++) {
            //相邻元素比较,顺序错误则交换
            if(arr[j]>arr[j+1]) {
                int temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
        }
    }
}



1.5算法分析

平均时间复杂度：O(n

2

) ，内外两重循环都与数据规模n相关。

最好时间复杂度：O(n)，当原本就有序，且在第一趟外循环结束时就判断出序列有序直接退出排序。如下。

最坏时间复杂度：O(n

2

)，当原本逆序时。

空间复杂度：O(1)，代码执行所需空间与数据规模n无关。

稳定性：稳定，

if(arr[j]>arr[j+1]){}

，相等元素其相对位置不会改变。

注意：可设置标记，判断是否已经有序，从而小小优化冒泡排序算法。 

for(int i=0;i<len-1;i++) {
	int flag = 1;	//记录的标记
	for(int j=0;j<len-i-1;j++) {
		if(arr[j]>arr[j+1]) {
			int temp = arr[j];
			arr[j] = arr[j+1];
			arr[j+1] = temp;
			//有交换位置说明该数组不是有序的，标记置为0
			flag = 0;			
		}
	}
	//第一趟比较后，若flag==1则证明数组有序，直接退出，无需后面的操作。
	if(flag==1)	break;
}



2.0快速排序（Quick Sort）



2.1基本思想

冒泡排序的改进。

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



2.2动图演示

快速排序



2.3算法描述

分治法，将待排序序列依据选择的基准分成两个子序列，再递归的处理子序列。

  1. 从序列中选择一个数作为基准，它划分的两序列长度越接近，则快排越高效。（如：第一个、最后一个、随机位置的一个等等）。
  2. 依据基准采用算法将序列划分成两个子序列。
  3. 递归的处理这两个子序列。



2.4代码实现

public static void quickSort(int arr[],int start,int end) {
    int i;    //基准下标的指示器
    if(start<end)         //区间存在两个及两个以上的元素,进行快排
    {
        i = SortTest.partition(arr, start, end);   //划分后基准的位置
        SortTest.quickSort(arr, start, i-1);       //左区间递归排序
        SortTest.quickSort(arr, i+1, end);         //右区间递归排序
    }
}

/**
* -一趟划分,选取一个基准将无序区分为两部分,一部分比基准小,另一部分比基准大，等于基准的随意
*/
public static int partition(int arr[],int start,int end) {
    int i=start,j=end;     //设置两个指示器,指向头和尾
    int temp = arr[i];     //选取基准，这里选取第一个元素做划分基准

    //从两端向中间扫描,直至指示器 i=j 为止
    while(i<j) {
        //从右向左扫描,找到一个小于 temp 的 arr[j]
        while(j>i && arr[j]>=temp) {
            j--;
        }
        arr[i] = arr[j];   //找到这样的 arr[j],放到arr[i]处

        //从左向右扫描,找到一个大于 temp 的 arr[i]
        while(i<j && arr[i]<=temp) {
            i++;
        }
        arr[j] = arr[i];   //找到这样的 arr[i],放到arr[j]处
    }

    arr[i] = temp;    //划分完毕,基准回到正确位置
    return i;         //返回此躺划分后的基准的下标
}



2.5算法分析

平均时间复杂度：O(nlogn)，划分和递归的快排。

最好时间复杂度：O(nlogn)。

最坏时间复杂度：O(n

2

)，当原本逆序时，退化成冒泡排序。

空间复杂度：O(logn)，就地排序，但每次递归要保持数据，故O(logn)。

稳定性：不稳定，当序列中有等于选出的基准的元素时，划分时相对位置可能改变。

注意：基准的选择决定着快排的效率，一般可随机选一个基准。



3.0插入排序（Insertion Sort）



3.1基本思想

也称直接插入排序。对少量且基本有序的序列较高效。

它通过构建有序序列，对于未排序数据，在已排序的序列中从后向前扫描，找到相应位置并插入。



3.2动图演示

直接插入排序



3.3算法描述

  1. 初始时：有序区 arr[0]，无序区 arr[1…len-1]。
  2. 取无序区的第一个元素，在有序区中从后往前的扫描。
  3. 若取出元素小于当前元素，则当前元素后移，一直往前扫描，直到不小于当前元素时，记录此下标。
  4. 将取出的元素插入到此下标指向的位置，一次插入结束。无序区减1。
  5. 重复2-4，直到无序区为空。



3.4代码实现

public static void insertSort(int arr[]) {
    int preIndex;   //当前元素的前驱元素的下标
    int current;    //当前元素
    int len = arr.length;  //数组的长度

    for(int i=1;i<len;i++) {
        preIndex = i-1;
        current = arr[i];
        while(preIndex>=0 && current<arr[preIndex]) {
            arr[preIndex+1] = arr[preIndex];
            preIndex--;
        }
        arr[preIndex+1] = current;
    }
}



3.5算法分析

平均时间复杂度：O(n

2

)，两层循环。

最好时间复杂度：O(n)。当原本有序，则内循环不执行。

最坏时间复杂度：O(n

2

)，当原本逆序时。

空间复杂度：O(1)，就地排序。

稳定性：稳定。



4.0希尔排序（Shell Sort）



4.1基本思想

也称“缩小增量排序”。插入排序的改进版。

它把序列按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的元素越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。



4.2动图演示

希尔排序



4.3算法描述

  1. 确定增量。d=len/2，原序列分为两组。
  2. 每组采用直接插入排序。
  3. 减小增量，d=d/2，再分组。
  4. 重复2,3，直到增量为1时，只有一组，排序完成。



4.4代码实现

public static void shellSort(int arr[]) {
    int len = arr.length; //数组的长度
    int d =len/2;         //增量置初值     
    while(d>=1) {
        for(int i=d;i<len;i++) {
            //对所有组采用直接插入排序
            int current = arr[i];
            int j = i-d;             //对相隔d个位置的一组采用直接插入排序
            while(j>=0 && current<arr[j]) {
                arr[j+d] = arr[j];
                j = j-d;
            }
            arr[j+d] = current;
        }
        d = d/2;        //减小增量
    }
}



4.5算法分析

平均时间复杂度：O(n

1.3

)，找度娘。

最好时间复杂度：O(n)。当原本有序，则内循环不执行。

最坏时间复杂度：O(n

2

)，当原本逆序时。

空间复杂度：O(1)，就地排序。

稳定性：不稳定，插入排序是稳定，但希尔排序是有间隔的分组插入排序。

注意：增量的选择决定希尔排序的效率。



5.0选择排序（Select Sort）



5.1基本思想

未排序序列中找到最小(最大)元素，存放到已排序序列的末尾。



5.2动图演示

选择排序



5.3算法描述

  1. 初始时认为无序区第一个元素最小，记录下标。
  2. 遍历得到无序区的最小元素，记录下标。
  3. 两者相等则下一轮循环，否则交换位置后再进入下一轮循环。
  4. 重复1、2、3，直到无序区空。



5.4代码实现

public static void selectSort(int arr[]) {
    int len = arr.length;  //数组元素的个数

    //第 i 趟排序
    for(int i=0;i<len-1;i++) {
        int index = i;         //保存无序区中最小元素的下标

        //后边的元素都与已知的最小的元素比较,以便找到整个无序区中最小的元素
        for(int j=i+1;j<len;j++) {
            if(arr[j]<arr[index]) {
                index = j;    //保存无序区最小元素的下标
            }
        }

        //若此趟排序找到的最小元素下标不是默认的无序区第一个元素,则交换位置
        if(i!=index) {
            int temp = arr[i];
            arr[i] = arr[index];
            arr[index] = temp;
        }
    }
}



5.5算法分析

平均时间复杂度：O(n

2

)，两重循环。

最好时间复杂度：O(n

2

)。当原本有序，依旧要进行内循环的遍历才能确定最小元素。

最坏时间复杂度：O(n

2

)，当原本逆序时。

空间复杂度：O(1)，就地排序。

稳定性：不稳定，比如：{5

left

,8,5

right

,2,9}，排序后：{2,5

right

,5

left

,8,9}，两个5的相对位置改变。



6.0堆排序（Heap Sort）



6.1基本思想


利用堆这种数据结构

所设计的一种排序算法。堆是一个近似完全二叉树的结构，并同时满足

堆积

的性质：即子结点的键值或索引总是小于（或大于）它的父节点。堆排序可以说是一种

利用堆的概念来排序的选择排序

。分为两种方法：

大顶堆：每个节点的值都大于或等于其子节点的值，在堆排序算法中用于升序排列；

小顶堆：每个节点的值都小于或等于其子节点的值，在堆排序算法中用于降序排列；



6.2动图演示

堆排序
堆排序



6.3算法描述

  1. 升序排列，建造大顶堆，然后堆顶和堆尾元素交换(则最大的就到了末尾)，堆中元素个数减1。
  2. 默认 arr[0…len-1] 构成大顶堆，从最后一个有子节点的节点处向上调整，使满足堆积。
  3. 堆顶元素和堆尾元素交换位置(此时堆尾元素最大)，堆中元素个数减1。
  4. 从堆顶处向下调整，使满足堆积。
  5. 重复3、4，直到堆中元素为0则堆排序结束。



6.4代码实现

private static int len;		//记录未排序数组的长度
public static void heapSort(int[] arr) {
    len = arr.length;
    if(arr==null || len<=2)
        return;

    //初始化大顶堆，最后一个有子节点的元素的下标
    for(int i=(len/2-1);i>=0;i--) {
        heapify(arr, i);
    }

    for(int i=arr.length-1;i>=0;i--) {
        //将大顶堆的堆顶元素和堆尾元素交换
        int temp = arr[0]; arr[0] = arr[i]; arr[i] = temp;
        len--;
        heapify(arr, 0);
    }
}

/**
* -堆化函数：调整第i个位置的元素，使满足大顶堆
*/
public static void heapify(int[] arr,int i) {
    int left  = 2*i+1;
    int right = left+1;
    int max   = i;

    if(left<len && arr[left]>arr[max])
        max = left;
    if(right<len && arr[right]>arr[max])
        max = right;

    if(max!=i) {
        //交换下标对应的元素
        int temp = arr[i]; arr[i] = arr[max]; arr[max] = temp;
        //交换元素之后，对可能被破坏的大顶堆继续堆化
        heapify(arr, max);
    }
}



6.5算法分析

平均时间复杂度：O(nlogn)。每轮选择一个最大数，且进行堆化调整。

最好时间复杂度：O(nlogn)。

最坏时间复杂度：O(nlogn)。

空间复杂度：O(1)，就地排序。

稳定性：不稳定。同选择排序。



7.0归并排序（Merge Sort）



7.1基本思想

归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。

将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。



7.2动图演示

归并排序

归并排序



7.3算法描述

  1. 将长度为

    len

    的序列划分成两个

    len/2

    的子序列。
  2. 对这两个子序列再归并排序。
  3. 合并这两个已经排好序的序列。



7.4代码实现

public static int[] mergeSort(int arr[]) {
    if(arr==null || arr.length<2)
        return arr;

    int mid = arr.length/2;
    int[] left  = Arrays.copyOfRange(arr, 0, mid);	//使用	[from,to)	的元素生成新数组
    int[] right = Arrays.copyOfRange(arr, mid, arr.length);	//native实现，效率高

    //对子序列使用归并排序
    return merge(mergeSort(left),mergeSort(right));
}
//将两个有序的序列合并成一个有序的序列
public static int[] merge(int[] left,int[] right) {
    int[] result = new int[left.length + right.length];

    int indexResult = 0;
    int indexLeft   = 0;
    int indexRight  = 0;

    while(indexResult!=result.length) {
        if(indexLeft >= left.length)
            result[indexResult++] = right[indexRight++];
        else if(indexRight >= right.length)
            result[indexResult++] = left[indexLeft++];
        else if(left[indexLeft] <= right[indexRight])
            result[indexResult++] = left[indexLeft++];
        else
            result[indexResult++] = right[indexRight++];
    }

    return result;
}



7.5算法分析

平均时间复杂度：O(nlogn)。总时间=分解时间+解决问题时间+合并时间=O(1)+2O(n/2)+O(n)。

最好时间复杂度：O(nlogn)。

最坏时间复杂度：O(nlogn)。

空间复杂度：O(n)，临时的数组和递归时压入栈的数据占用的空间：n + logn。

稳定性：稳定。

注意：1.虽然时间复杂度为O(nlogn)，却消耗空间。故一般外排序才会用它。内排序用快排。



7.6递归式的时间复杂度

递归图

对于2O(n/2)这个递归式可以用递归树来求解。

假设解决最后的子问题用时为常数c，则每一层递归花费时间都为cn，总共有log

2

n层的递归。

故递归耗时cn*(log

2

n)。

O(nlogn)。



8.0计数排序（Countint Sort）



8.1基本思想

核心：将输入的数据值转化为键存储在额外开辟的数组空间中。作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。



8.2动图演示

计数排序



8.3算法描述

  1. 确定输入数据的极差，开辟数组存放数值(下标相关)，及其出现的次数(下标对应的值)。
  2. 遍历待排序数组，填充开辟的用于计数的数组。
  3. 遍历计数的数组，填充排好序的数组。



8.4代码实现

public static int[] countingSort(int[] arr) {
    int min = arr[0];
    int max = arr[0];
    int len = arr.length;

    if(arr==null || len<=2)
        return null;

    //确定极差，优化额外开辟的数组
    for(int temp:arr) {
        if(temp<min)
            min = temp;
        if(temp>max)
            max = temp;
    }

    //额外开辟的空间，存储原数组的计数信息
    int k = max-min+1;
    int[] count = new int[k];

    //遍历原数组，填充用于计数的数组
    for(int i=0;i<len;i++) {
        count[arr[i]-min]++;
    }

    //遍历计数的数组，填充排好序的数组
    int[] res = new int[len];
    int resIndex = 0;
    for(int i=0;i<k;i++) {
        while(count[i]>0) {
            res[resIndex] =  i+min;
            resIndex++;
            count[i]--;
        }
    }

    return res;
}



8.5算法分析

平均时间复杂度：O(n+k)。数据规模n，数据间极差k。

最好时间复杂度：O(n+k)。

最坏时间复杂度：O(n+k)。

空间复杂度：O(n+k)，返回的结果数据组n，用于计数的数组k。

稳定性：稳定。反向填充结果数组保证其稳定性。



9.0桶排序（Bucket Sort）



9.1基本思想

桶排序是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。为了使桶排序更加高效，我们需要做到这两点：

  1. 在额外空间充足的情况下，尽量增大桶的数量。
  2. 使用的映射函数能够将输入的 N 个数据均匀的分配到 K 个桶中。

同时，对于桶中元素的排序，选择何种比较排序算法对于性能的影响至关重要。



9.2动图演示

桶排序



9.3算法描述

  1. 设置一定量的桶，遍历数组，按照某种映射关系入桶。
  2. 遍历桶，桶内采用某种算法进行桶内排序。
  3. 所有桶数据输出。



9.4代码实现

public static void bucketSort(int[] arr) {
    int len = arr.length;
    int min = arr[0];
    int max = arr[0];

    if(arr==null || len<=2)
        return;

    //得数组元素的极差
    for(int temp:arr) {
        if(temp<min)
            min = temp;
        if(temp>max)
            max = temp;
    }

    final int DEFALT_BUCKET_SIZE = 5;		//默认桶的大小，可存放多少个不同的数字
    int bucketCount = (max-min)/DEFALT_BUCKET_SIZE + 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 < len; i++) {
        bucketArr.get((arr[i] - min) / DEFALT_BUCKET_SIZE).add(arr[i]);	//映射关系入桶
    }

    //遍历桶，对每个桶进行排序，然后输出数组
    for (int i = 0; i < bucketCount; i++) {
        //对这个桶排序，桶内排序
        bucketArr.get(i).sort((Integer o1,Integer o2) -> {return o1.compareTo(o2);});
        //排序后加入结果集
        resultArr.addAll(bucketArr.get(i));
    }

    //排序后的结果替换原数组
    for(int i=0;i<len;i++) {
        arr[i] = resultArr.get(i);
    }
}



9.5算法分析

平均时间复杂度：O(n+k)。数据规模n，桶的数量k。

最好时间复杂度：O(n)，每个桶只有一个数据。

最坏时间复杂度：O(n

2

)，数据都在一个桶。

空间复杂度：O(n+k)，返回的结果数据组n，桶数组k。

稳定性：稳定。



10.0基数排序（Radix Sort）



10.1基本思想

基数排序是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别归类。由于整数也可以表达字符串（比如名字或日期）和特定格式的浮点数，所以基数排序也不是只能使用于整数。

1.最高为优先。

2.最低位优先。



10.2动图演示

基数排序



10.3算法描述

  1. 把每个数从最高位(或最低位)开始，依次取出一个数组成radix数组。
  2. 对radix进行计数排序，(计数排序适用于小范围数的特点)。



10.4代码实现

public static void radixSort(int[] arr) {
    if(arr==null || arr.length<=2)
        return;

    int len = arr.length;
    //得到数组的最大值
    int max = arr[0];
    for(int temp:arr) {
        if(temp>max)
            max = temp;
    }

    //数组中最大数的位数：比如 max=98,则 maxLen=2
    int maxLen = 0;
    while(max!=0) {
        maxLen++;
        max /= 10;
    }

    List<ArrayList<Integer>> bucket = new ArrayList<ArrayList<Integer>>();//桶列表，有10个桶
    for(int i=0;i<10;i++)
        bucket.add(new ArrayList<Integer>());	//为桶分配空间

    int mod = 10, div = 1;
    for(int i=0;i<maxLen;i++,div*=10) {
        ArrayList<Integer> temp = new ArrayList<Integer>();
        for(int j=0;j<len;j++) {
            int num = (arr[j]/div)%mod;		//取出该数的第几个数字
            bucket.get(num).add(arr[j]);	//这个数字是几，就放到第几个桶
        }

        //遍历桶，按照顺序取值覆盖原数组
        for(int k=0;k<10;k++) {
            temp.addAll(bucket.get(k));
        }

        int index = 0;
        for(int tmp:temp) {
            arr[index++] = tmp;
        }
    }
}



10.5算法分析

平均时间复杂度：O(n*k)。数据规模n，待排序数据可分为k个关键字。

最好时间复杂度：O(n*k)。

最坏时间复杂度：O(n*k)。

空间复杂度：O(n+k)。桶数量k。

稳定性：稳定。


版权声明：本文为qq_40896594原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。