排序算法

Author Avatar
ahscuml 7月 24, 2018
  • 在其它设备中阅读本文章

基于网络课程和《数据结构与算法分析——Java语言描述》，基本排序算法的讲解，以及Java代码实现。

O(n²) 时间复杂度
虽然时间复杂度相对较高，但是同样也有好处

  • 编码相对简单
  • 在某些情况下，这些算法反而更有效
  • 可以从简单的方法中衍生出复杂的算法
  • 作为子过程，经过修改变为复杂的算法

重要的思想：
逆序数：排序的过程就是消除逆序数的过程，所以逆序数的个数影响排序的性能(也可以从这个角度来思考排序的性能)

  • N个互异数的数组的平均逆序数是 $ N(N-1)/4 $(数对的一半)
  • 通过交换相邻元素进行排序的任何算法平均都需要 $ Ω(N^2) $
  • 对于归并排序，归并过程中，可以一次消除多个逆序数，提高算法效率。

选择排序 Selection Sort

从未排序的数组中逐一选择最小的元素进行排序
KEY：寻找数组中最小的元素
大约需要 $\frac{N^2}{2}$次比较和N次交换
可以考虑对算法进行升级，不仅仅对整型进行排序，对浮点型甚至对对象进行排序（采用Comparable接口，然后通过compareto进行比较）
特点：

  • 运行时间和输入无关(这样对于最开始就基本有序的数组就没有优势了)
  • 数据移动最少

算法实现

public class SelectionSort{
    public static void SelectionSort(Comparable[] arr) {
        int n = arr.length;
        for (int i = 0; i < n; i++) {
            int minindex = i;
            //注意是从i+1开始的
            for (int j = i + 1; j < n; j++) {
                if(arr[j].compareTo(arr[minindxe]) < 0){
                    minindex = j;
                }
            }
            swap(arr,minindex,i);
        }
    }
    public static void swap(Object[] arr, int i, int j){
        Object e = arr[i];
        arr[i] = arr[j];
        arr[j] = e;
    }
}

选择排序优化

优化前，一次遍历仅仅可以找到最小的排好序，优化后，一次遍历可以找到最小的以及最大的两个元素排好序

public class SelectionSort {
    public static void selectionSort(Comparable[] arr) {
        int n = arr.length;
        int left = 0, right = n - 1;
        while(left < right){
            int minindex = left, maxindex = right;
            if(arr[minindex].compareTo(arr[maxindex]) > 0)
                swap(arr, minindex, maxindex);
                //注意i的范围
            for(int i = left + 1; i < right; i++) {
                if (arr[i].compareTo(arr[minindex]) < 0) {
                    minindex = i;
                }
                if (arr[i].compareTo(arr[maxindex]) > 0) {
                    maxindex = i;
                }
            }
            swap(arr, left, minindex);
            swap(arr, right, maxindex);
            left++;
            right--;
        }
    }
}

插入排序 Insertion Sort

插入排序由N-1趟排序组成。对于p到N-1趟，插入排序保证从位置0到位置p上的元素为已排状态。
KEY:比前面一个小就进行交换，否则结束这一次插入(比选择排序优秀的地方，可以提前结束)

  • 平均情况下，插入排序需要$\frac{N^2}{4}$次比较与$\frac{N^2}{4}$次交换
  • 逆序数思考维度，每一次交换都是在减少一个逆序数，那么就需要逆序数次交换。

  • 对插入排序进行优化：之前的插入排序每一次插入都要进行很多次交换，然而每次交换都是三次赋值的时间，所以很浪费时间，这样可以牺牲一个时间复杂度，将要插入的元素跟之前的元素进行比较，但是先不交换，等到找到要交换的元素，再进行一次交换，这样每一次插入都只进行一次交换。

    复杂度分析

    插入排序为$O(n^2)$,如果输入数组时反序的时候，复杂度为$\Theta(N^2)$,如果输入已经预先排序，那么复杂度为$O(N^2)$。正因如此如果输入几乎被排序，那么插入排序将运行的更快。

    算法实现

    public class InsertionSort{
  public static void insertionSort(Comparable arr) {
      int n = arr.length;
      for(int i = 0; i < n; i++) {
          // 寻找元素arr[i]合适的插入位置

          // 写法1
          // for( int j = i ; j > 0 ; j -- )
          //    if( arr[j].compareTo( arr[j-1] ) < 0 )
          //        swap( arr, j , j-1 );
          //    else
          //        break;

          // 写法2
//            for( int j = i; j > 0 && arr[j].compareTo(arr[j-1]) < 0 ; j--)
//                swap(arr, j, j-1);

          // 写法3
          // 改进的插入算法，利用赋值替代交换，减少时间消耗
          Comparable e = arr[i];
          int j = i;
          for( ; j > 0 && arr[j-1].compareTo(e) > 0 ; j--)
              arr[j] = arr[j-1];
          arr[j] = e;
      }
  }
  public static void swap(Object[] arr, int i, int j){
      Object e = arr[i];
      arr[i] = arr[j];
      arr[j] = e;
  }
}

冒泡排序 Bubble Sort

它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。 

public class ShellSort {
    private ShellSort() {
    }

    /**
     * 希尔排序算法
     */
    public static void sort(Comparable[] arr) {
        int n = arr.length;
        int h = 1;
        while (h < n / 3) {
            h = 3 * h + 1;
        }
        while (h >= 1) {
            // 排序是从h到n
            for (int i = h; i < n; i++) {
                Comparable e = arr[i];
                int j = i;
                for (; j >= h && e.compareTo(arr[j - h]) < 0; j -= h) {
                    arr[j] = arr[j - h];
                }
                arr[j] = e;
            }
            h /= 3;
        }
    }

    /**
     * 测试用例
     */
    public static void main(String[] args) {
        int N = 1000000;
        Integer[] arr = SortTestHelper.generateRandomArray(N, 0, 100000);
        SortTestHelper.testSort("sort.ShellSort", arr);
    }
}

希尔排序 Shell Sort

  • 希尔排序通过比较一定间隔的元素来工作，，各趟比较所用的距离随着算法的进行而减小，直到只比较相邻元素的最后一趟排序为止。
  • $h_k$排序的一般做法是，对于$h_k$，$h_{k+1}$，···$N-1$中的每一个位置i,把其上的元素放到i，$i-h_k$,$i-2h_k$,···中的正确位置上。

    算法分析

  • 希尔排序的一个重要性质就是一个$h_k$排序的文件保持它的$h_k$排序性(我的理解就是，经过$h_k$排序后，逆序对不会再增加)
  • 使用希尔增量时希尔排序的最坏情形运行时间为$\Theta(N^2)$
    public class ShellSort {
  privata ShellSort(){}
  public static void shellSort(Comparable[] arr){
      for(int gap = arr.length/2; gap < arr.length; gap /= 2) {
          for(int i = gap; i < arr.length; i++) {
              // 使用插入排序
              Comparable[] temp = arr[i];
              int j = i;
              for(; j >= gap && temp.compareTo(arr[j - gap]) <0; j-=gap){
                  a[j] = a[j - gap];
              }
              a[j] = temp;
          }
      }
  }
}

O(nlgn)复杂度的排序算法
分治算法的思想(分而治之)

归并排序 重点在合(如何合)
快速排序 重点在分(如何分)

归并排序 Merge Sort

KEY：将两个有序的数组合并为一个有序的数组
牺牲了存储空间，获得了时间上的减少。
首先进行分层，然后对每一层使用归并排序
归并排序的逻辑 递归的思想，这也是递归的一个很好的例子。对于递归的效率分析也是一个很好的技巧(叠缩求和与带入法)
优化：

  • 对近乎有序的数组进行优化要判断要不要进行归并
  • 由于对于小数据量的元素使用插入排序更加迅速， 所及可以考虑分层进行到一部分的时候改用插入排序(一部分是怎么确定的？)

优化后的归并排序

public class MergeSort {
    private MergeSort() {
    }

    /**
     * 递归使用归并排序，对arr[l...r]的范围进行排序
     */
    private static void sort(Comparable[] arr, int l, int r) {
        /*if(l>=r){
            return;
        }*/
        // 优化2：在归并到一定程度的时候使用插入排序
        int size = 15;
        if (r - l <= size) {
            insertionSort(arr, l, r);
        }
        // int mid = (r - l) / 2 + l;
        int mid = (l + r) / 2;
        sort(arr, l, mid);
        sort(arr, mid + 1, r);
        // 优化1：如果已经有序就不进行归并了。
        if (arr[mid].compareTo(arr[mid + 1]) > 0) {
            merge(arr, l, mid, r);
        }
    }
    /**
     * 将arr[l...mid]和arr[mid+1...r]两部分进行归并
     */
    private static void merge(Comparable[] arr, int l, int mid, int r) {
        //拷贝一个数组赋值用(牺牲空间复杂度，降低时间复杂度)
        //注意还有个+1
        Comparable[] aux = Arrays.copyOfRange(arr, l, r + 1);
                // 初始化，i指向左半部分的起始索引位置l；j指向右半部分起始索引位置mid+1
        int i = l, j = mid + 1;
        for (int k = l; k <= r; k++) {
            // 如果左半部分元素已经全部处理完毕
            if (i > mid) {
                // j - l很关键
                arr[k] = aux[j - l];
                j++;
                // 如果右半部分元素已经全部处理完毕
            } else if (j > r) {
                arr[k] = aux[i - l];
                i++;
                // 左半部分所指元素 < 右半部分所指元素
            } else if (aux[i - l].compareTo(aux[j - l]) < 0) {
                arr[k] = aux[i - l];
                i++;
                // 左半部分所指元素 >= 右半部分所指元素
            } else {
                arr[k] = arr[j - l];
                j++;
            }
        }
    }
    private static void insertionSort(Comparable[] arr, int l, int r) {
        for (int i = l + 1; i <= r; i++) {
            int j = i;
            Comparable e = arr[j];
            for (; j > l; j--) {
                if (e.compareTo(arr[j - 1]) < 0) {
                    arr[j] = arr[j - 1];
                } else {
                    break;
                }
            }
            arr[j] = e;
        }
    }
}

自底向上的归并排序

不使用递归，只用迭代性能相对来说要差一点点
并没有使用到数组的特性(通过下标寻找元素)，所以对于链表很适用。
对于数组要思考到越界的问题 

public class MergeSortBUAdvanced{
    /**
     * 自底向上归并排序优化
     * 1、在size小的时候采用插入排序
     * 2、如果归并之前已经有序，则不进行归并
     */
    public static void sort(Comparable[] arr) {
        int n = arr.length;
        // 设置size，低于这个size使用插入排序
        int size = 16;
        // 优化1： 小数组使用插入排序更优化
        for (int i = 0; i < n; i += size) {
            insertionSort(arr, i, Math.min(i + size - 1, n - 1));
        }
        for (; size < n; size += size) {
            for (int i = 0; i + size  < n; i += size + size) {
                // 优化2： 如果之前已经有序，则不进行归并
                if (arr[i + size - 1].compareTo(arr[i + size]) > 0) {
                    merge(arr, i, i + size - 1, Math.min(i + size + size - 1, n - 1));
                }
            }
        }
    }

    private static void merge(Comparable[] arr, int l, int mid, int r) {
        Comparable[] aux = Arrays.copyOfRange(arr, l, r + 1);
        int i = l, j = mid + 1;
        for (int k = l; k <= r; k++) {
            if (i > mid) {
                arr[k] = aux[j - l];
                j++;
            } else if (j > r) {
                arr[k] = aux[i - l];
                i++;
            } else if (aux[i - l].compareTo(aux[j - l]) < 0) {
                arr[k] = aux[i - l];
                i++;
            } else {
                arr[k] = aux[j - l];
                j++;
            }
        }
    }
    // 优化中使用的插入排序
    private static void insertionSort(Comparable[] arr, int l, int r) {
        for (int i = l; i <= r; i++) {
            Comparable e = arr[i];
            int j = i;
            for (; j > l; j--) {
                if (e.compareTo(arr[j - 1]) < 0) {
                    arr[j] = arr[j - 1];
                } else {
                    break;
                }
            }
            arr[j] = e;
        }
    }
}

问题：求逆序数个数

对递归的理解很关键，通过运用归并排序的方法，使得求逆序数的复杂度变为 $O(nlogn$

public class InversionCount{
    /**
     * 递归排序(用作分割)
     */
    public static long sort(Comparable[] arr, int l, int r) {
        if (l >= r) {
            return 0L;
        }
        int mid = l + (r - l) / 2;
        // 求出 arr[l...mid] 范围的逆序数
        long countl = sort(arr, l, mid);
        // 求出 arr[mid+1...r] 范围的逆序数
        long countr = sort(arr, mid + 1, r);
        // 两个count分别是上一个merge的结果，这就相当于将所有的merge结果相加
        return countl + countr + merge(arr, l, mid, r);
    }

    /**
     * 合并操作,就是一个排序的过程
     */
    private static long merge(Comparable[] arr, int l, int mid, int r) {
        // 逆序数对个数初始化
        long count = 0L;
        // merge操作
        Comparable[] aux = Arrays.copyOfRange(arr, l, r + 1);
        int i = l, j = mid + 1;
        for (int k = l; k <= r; k++) {  // 如果左半部分元素已经全部处理完毕
            if (i > mid) {
                arr[k] = aux[j - l];
                j++;
            } else if (j > r) {  // 如果右半部分元素已经全部处理完毕
                arr[k] = aux[i - l];
                i++;
            } else if (aux[j - l].compareTo(aux[i - l]) >= 0) {  // 左半部分所指元素 <= 右半部分所指元素
                arr[k] = aux[i - l];
                i++;
            } else { // 右半部分所指元素 < 左半部分所指元素
                arr[k] = aux[j - l];
                j++;
                // 此时, 因为右半部分j所指的元素小
                // 这个元素和左半部分的所有未处理的元素都构成了逆序数对(不包括右边的是因为右边的在上一次迭代的时候已经计算过了)
                // 左半部分此时未处理的元素个数为 mid - i + 1(注意i的意思，i是将要处理的元素)
                count = count + (long) (mid - i + 1);
            }
        }
        return count;
    }
}

快速排序 Quick Sort

key:如何将数组分为大小两个(Partition)
递归思想，分别使用快速排序
围绕着枢纽元进行大小分离，不进行排序，只区分大小

简单快速排序(注意数组的边界)

  1. 首先确定元素$v$
  2. 遍历数组(j是$<v$的尾部，i是$>v$的尾部,e是遍历的元素)
    快速排序结构1
  3. 遍历一遍的数组结构
    快速排序结构2
  4. 最终的结构，j是选定元素的下标，左边是小于$v$的元素，右面是大于$v$的元素
    快速排序结构3
public class QuickSort{
    public static void quickSort(Comparable[] arr, int l, int r){
        // 递归的基准情况
        if (l >= r) {
            return;
        }
        // partion操作，移动元素，找到中值的位置
        Comparable v = arr[l];
        int j = l;
        for (int i = l + 1; i <= r; i++) {
            if (arr[i].compareTo(v) < 0) {
                j++;
                swap(arr, j, i);
            } 
        }
        swap(arr, l, j);
        j--;
        // 进行递归
        quickSort(arr, l, j);
        quickSort(arr, j + 2, r);
    }
    // 交换函数
    private static void swap(Comparable[] arr, int i, int j) {
        Comparable temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

快速排序的优化

重点关注列表中下标的位置，根据整个流程来编写程序，同时在分界点，根据下标来区分。

  1. 底层可以采用插入排序的算法进行优化
  2. 针对 近乎有序 数组的优化。和归并排序比较，都是利用递归，同样将数组一分为二，但是归并左右两部分是平衡的而快速排序却不是(根据元素的选择)。 不再采用第一个元素为中间值，采用随机选取元素作为中间值。
  3. 针对有 重复元素 的数组进行的优化。由于在对数组进行分类的时候，与中间值相等的元素并没有进行考虑，所以仍旧被分到了两侧，这样下一次排序仍然要对这些元素进行比较，导致速度很慢。 可以考虑在分类的时候，将大的元素从后往前放置，小的元素从前往后放置，将与中间值相等的元素分散到两侧，这样对于有大量的相同元素的数组可以避免一边数据量很大造成不平衡。
    • 新的算法思想(QuickSort2Ways)
    1. 改变放置的方式
      QuickSortAdvanced
    2. 继续从i开始向后遍历元素，直到找到元素$>=v$。
      QuickSortAdvanced
    3. 继续从j开始向前遍历元素，直到找到元素$<=v$。
      QuickSortAdvanced
    4. 然后交换i的元素和j的元素
      QuickSortAdvanced
    5. 继续遍历，直到i=j遍历完成
public class QuickSort2Ways {
   public static void QuickSort2Ways(Comparable[] arr, int l, int r) {
        // 优化：小数组采用插入排序, 递归的基准情况
        int size = 16;
        if (r - l <= size - 1) {
            insertionSort(arr, l, r);
            return;
        }
        // 优化：随机选择中间值，避免过多相同元素的情况
        swap(arr, l, (int) Math.random() * (r - l + 1) + l);
        // 优化：两路排序
        Comparable v = arr[l];
        int i = l + 1, j = r;
        while (true) {
            // 为什么是 < 不是 <= 的思考(http://coding.imooc.com/learn/questiondetail/4920.html)
            while (i <= r && arr[i].compareTo(v) < 0) {
                i++;
            }
            while (j >= l + 1 && arr[j].compareTo(v) > 0) {
                j--;
            }
            // 跳出循环
            if (i > j) {
                break;
            }
            swap(arr, i, j);
            i++;
            j--;
        }
        swap(arr, l, j);
        // 递归调用
        sort(arr, l, j - 1);
        sort(arr, j + 1, r);
    }

    private static void swap(Comparable[] arr, int i, int j) {
        Comparable temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    private static void insertionSort(Comparable[] arr, int l, int r) {
        for (int i = l; i < r; i++) {
            Comparable e = arr[i];
            int j = i;
            for (; j > l; j--) {
                if (arr[j - 1].compareTo(e) > 0) {
                    arr[j] = arr[j - 1];
                } else {
                    break;
                }
            }
            arr[j] = e;
        }
    }
}
  1. 在QuickSort2Ways的基础之上对于选定元素相等的元素也进行分类，产生QuickSort3Ways.
    • 终极算法QuickSort3Ways
    1. 开始的状态，同时维护3路元素，分别是$>v$、$<v$、$=v$。初始阶段如下图，注意边界的值！
      QuickSort3Ways
    2. 如果元素$e$与元素$v$相等，则将i向后移动一位
      QuickSort3Ways
    3. 如果元素$e$比元素$v$小，则将$e$与 =$v$ 的元素块第一个元素(lt+1)交换,i向后移动一位
      QuickSort3Ways
    4. 如果元素$e$比元素$v$大，则将$e$与 >$v$ 的元素块第一个元素(gt-1)交换,i向后移动一位
      QuickSort3Ways
    5. 最终的结果就是 i 与 gt 相等，遍历结束,最终还要讲lt位置的元素与第一个元素交换位置，得到最终的数组(如果不打算维护lt这个元素，要注意数组的边界位置)
      QuickSort3Ways
      QuickSort3Ways
public class QuickSort3Ways {
    /**
     * 3路快速排序算法
     */
    private static void QuickSort3Ways(Comparable[] arr, int l, int r) {
        // 优化1：在小分组的时候使用插入排序
        int size = 16;
        if (r - l <= size - 1) {
            insertionSort(arr, l, r);
            return;
        }
        // 优化2：随机选取元素的中间值，避免大量重复元素
        swap(arr, l, (int) Math.random() * (r - l + 1) + l);
        Comparable v = arr[l];
        // gt从r+1开始
        int lt = l, gt = r + 1, i = l + 1;
        while (i < gt) {
            if(v.compareTo(arr[i]) > 0) {
                lt++;
                swap(arr,i,lt);
                i++;
            } else if(v.compareTo(arr[i]) < 0) {
                // 交换了一个没有判断过的元素到i，所以i不用+1！
                gt--;
                swap(arr,i,gt);
            } else {
                // 两个元素相等的情况，不用进行交换
                i++;
            }
        }
        // 将第一个元素交换到=v的位置
        swap(arr,l,lt);
        lt--;
        // 递归调用
        sort(arr,l,lt);
        sort(arr,gt,r);
    }

    /**
     * 插入排序算法
     */
    public static void insertionSort(Comparable[] arr, int l, int r) {
        for (int i = 1; i < r - l + 1; i++) {
            Comparable e = arr[i];
            int j = i;
            for (; j > 0; j--) {
                if (e.compareTo(arr[j - 1]) < 0) {
                    arr[j] = arr[j - 1];
                } else {
                    break;
                }
            }
            arr[j] = e;
        }
    }

    /**
     * 交换函数
     */
    private static void swap(Comparable[] arr, int i, int j) {
        Comparable temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

问题：取出数组中第n大的元素

如果利用先排序再找到第n个最大值，那么这个算法的复杂度为$O(nlogn)$,但是利用快速排序的思想可以很好的解决这个问题，使得复杂度变为$O(n)$

public static Comparable selection(Comparable[] arr, int k) {
        int n = arr.length;
        // 注意这里是k - 1，因为下标还包括0
        return selection(arr, 0, n - 1, k - 1);
}
private static Comparable selection(Comparable[] arr, int l, int r, int k) {
        // 避免函数越界
        if (l == r) {
            return arr[l];
        }
        swap(arr, l, (int) Math.random() * (r - l + 1) + l);
        Comparable v = arr[l];
        int j = l;
        for (int i = l + 1; i <= r; i++) {
            if (arr[i].compareTo(v) < 0) {
                j++;
                swap(arr, i, j);
            }
        }
        swap(arr, l, j);
        if (j  < k) {
            return selection(arr, j + 1, r, k);
        } else if (j > k) {
            return selection(arr,l,j - 1,k);
        } else {
            return arr[j];
        }
    }

    /**
     * 交换函数
     */
    private static void swap(Comparable[] arr, int i, int j) {
        Comparable temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

堆排序 HeapSort

重点在于堆这种数据结构
队列：
普通队列：按照时间顺序，先进先出，后进后出
优先队列：出队顺序和入队顺序和时间无关，和优先级有关

定理

  1. N个互异数的数组的平均逆序数是$\frac{N(N-1)}{4}$
  2. 通过交换相邻元素进行排序的任何算法平均都需要$\Omega(N^2)$ 一个排序算法通过删除逆序得以向前进行，而为了有效地进行，他必须使每次交换删除不止一个逆序

This blog is under a CC BY-NC-SA 4.0 Unported License
本文链接：https://ahscuml.github.io/排序算法/

Powered by Hexo
Theme - Material