2016-08-14

排序

基于比较的排序算法:

BUB - 冒泡排序

算法原理

1.比较相邻的元素，如果第一个比第二个大，就交换他们两个；

2.对每一对相邻的元素做同样的工作，从开始第一对到结尾的最后一对，比较完一轮，最大的元素就放到了最后一位；

3.针对所有元素重复以上步骤，除了最后一个；

4.持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较；

算法分析

时间复杂度

若文件的初始状态是正序的，一趟扫描即可完成排序。所需的关键字比较次数C和记录移动次数M均达到最小值：$C{min}=n-1$,$M{min}=0$

所以，冒泡排序最好的时间复杂度为O(n)。

若初始文件是反序的，需要进行$n-1$趟排序。每趟排序要进行$n-i$次关键字的比较(1≤i≤n-1)，且每次比较都必须移动记录三次来达到交换记录位置。在这种情况下，比较和移动次数均达到最大值：

$$
C_{max}=\frac{n(n-1)}{2}=O(n^2)
$$

$$
M_{max}=\frac{3n(n-1)}{2}=O(n^2)
$$

冒泡排序的最坏时间复杂度为:$O(n^2)$.

因此冒泡排序的总的平均时间复杂度为$O(n^2)$.

算法描述

示例代码

public static void bubbleSort(int arr[]){
  
  for(int i=0;i<aar.length;i++){
    boolean isSwap = false;
    //从第一位和第二位开始比较，每一轮最大的数都排到了最后
    for(int j=0; j<aar.length-i-1;j++){
      //如果前面的元素大于后面的元素，交换位置
      if(arr[j]>arr{j+1}){
        int temp = arr[j];
        arr[j] = arr[j+1];
        arr[j+1]=temp;
        isSwap = true;
      }
    }
    //如果没有换位，说明排序完成了
    if(!isSwap){
      break;
    }
  }
}

SEL - 选择排序

算法原理

算法分析

时间复杂度

算法描述

示例代码

private static void selectionSort(int[] a) {
       for (int i = 0; i < a.length; i++) {
           int min = i;
           for (int j = i+1; j < a.length; j++) {
               if (a[min] > a[j]) {
                   min=j;
               }
           }
           if (min != i) {
               int temp = a[min];
               a[min] = a[i];
               a[i] = temp;
           }
       }
   }

INS - 插入排序

算法原理

将第一个元素标记为已排序

遍历每个没有排序过的元素

“提取” 元素 X

i = 最后排序过元素的指数到 0 的遍历

如果现在排序过的元素 > 提取的元素

将排序过的元素向右移一格

否则：插入提取的元素

算法分析

时间复杂度

算法描述

示例代码

private static void insertionSort(int[] a) {
        for (int i = 1; i < a.length ; i++) {
            //第一个元素为一个有序部分，故而，从数组第二个元素提取
            int value = a[i];
            //依次和有序部分从后往前比较，
            for (int j = i - 1; j >0; j--) {
                //如果取出的元素小于有序部分的元素，
                if (a[j] > value) {
                    //那么有序部分的元素往后移动一位 即有序部分下标+1
                    a[j+1] = a[j];
                    //否则结束比较，提取元素插入最后移动的哪个元素的位置
                } else {
                    a[j+1] = value;
                    break;
                }
            }
        }
    }

MER - 归并排序 (递归实现)

/**
    *
    * @param 排序数组
    * @param 数组开头下标
    * @param 数组长度
    * @return
    */
   private static int[] mergeSort(int[] a, int l, int h) {
       if (l == h) {
           return new int[]{a[l]};
       }
       int middle = l+(h-l)/2;
       int[] leftArray = mergeSort(a, l, middle);
       int[] rightArray = mergeSort(a, middle+1, h);
       //新有序数组
       int[] newNum = new int[leftArray.length + rightArray.length];
       int leftIndex=0,rightIndex=0,newIndex=0;
       while (leftIndex < leftArray.length && rightIndex < rightArray.length) {
           newNum[newIndex++]= leftArray[leftIndex]<rightArray[rightIndex]?leftArray[leftIndex++]:rightArray[rightIndex++];
       }
       while (leftIndex < leftArray.length) {
           newNum[newIndex++] = leftArray[leftIndex++];
       }
       while (rightIndex < rightArray.length) {
           newNum[newIndex++] = rightArray[rightIndex++];
       }
       return newNum;
   }

QUI - 快速排序 (递归实现)

R-Q - 随机快速排序 (递归实现)

不基于比较的排序算法:

COU - 计数排序

RAD - 基数排序

本文标题:排序

文章作者:markee

发布时间:2016-08-14, 17:21:33

最后更新:2020-09-28, 18:59:58

原始链接:http://code.idea4j.com/2016/08/14/排序/

许可协议: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。