## 每日一题 - 重复数据排序优化

### 信息卡片

- 时间：2019-06-11
- tag：`Quike Sort`

### 题目描述

```
如果一个数组含有大量重复元素，我们应该选择什么样的排序方法，背后的理论依据是什么”？
```


### 参考答案

取决于数据分布如何

1. 如果数据的总类很少, 而且每个都有大量重复的元素, 那么使用计数排序, 那么这个时间复杂度能够达到O(N).
```java
public class CountSort {
  public int[] countSort(int[] array) {
    int max = array[0];
    for(int i=1; i<array.length; i++) {
      if(array[i]>max) {
        max = array[i];
      }
    }
    //创建计数数组
    int[] countArray = new int[max+1];
    for(int i=0; i<array.length; i++) {
      countArray[array[i]]++;
    }
    int index = 0;
    //创建返回数组
    int[] sortArray = new int[array.length];
    for(int i=0; i<countArray.length; i++) {
      for(int j=0; j<countArray[i]; j++) {
        sortArray[index++] = i;
      }
    }
    return sortArray;
  }
}
```
2. 如果数据没有明显的规律, 可以考虑快排. 其性能与pivot的选择有关. 如果每次partition过程中的pivot选择能够较好的平分数组, 那么快排的速度能够达到O(NlogN). 因此再选择pivot时候, 可以选择数组中几个中间大小的数字. 此外, 对于重复数量大的数据, 可以选择三路快排来排序. 最后, 因为再数据近乎有序的时候, 插入排序的速度可以达到O(N), 所以在数据近乎有序的时候, 我们使用插入排序来优化排序过程.

```java
private class QuickSort{

  // 快排转化成为插入排序的阈值
  private static final int INSERTION_SORT_THRESHOLD = 47;

  public void QuickSort(int[] a) {
      if (a.length > 0) {
          quickSort(a, 0, a.length - 1);
      }
  }

  private void swap(int[] arr, int a, int b) {
      int temp = arr[a];
      arr[a] = arr[b];
      arr[b] = temp;
  }

  private int choosePivotMedianOfThree(int[] a, int l, int r) {
    int mid = 0;
    if ((r-l+1) % 2 == 0) {
      mid = l + (r-l+1)/2 - 1;
    } else {
      mid = l + (r-l+1)/2;
    }

    // 只需要找出中位数即可，不需要交换
    if (((a[l]-a[mid]) * (a[l]-a[r])) <= 0) {
      return l;
    } else if (((a[mid]-a[l]) * (a[mid]-a[r])) <= 0) 	{
      return mid;
    } else {
      return r;
    }
  }

  private void quickSort(int[] a, int left, int right) {
      if (right <= left)
          return;

      // 在数据近乎有序的时候, 插入排序的性能近乎于O(N)
      if(right - left <= INSERTION_SORT_THRESHOLD) {
        insertSort(a, left, right)
      }

      /*
      * 工作指针
      * p指向序列左边等于pivot元素的位置
      * q指向序列右边等于Pivot元素的位置
      * i指向从左向右扫面时的元素
      * j指向从右向左扫描时的元素
      */
      int p, q, i, j;
      int pivot;// 锚点
      i = p = left;
      j = q = right - 1;


      /*
      * 每次总是取序列最右边/最优和最中间的元素的大小中间值为锚点
      */
      pivot = choosePivotMedianOfThree(a, left, right);

      //始终将第一个元素作为pivot, 若不是, 则与之交换
      if (pivot != left) {
        swap(a, pivot, left);
      }
      pivot = a[right];

      while (true) {
          /*
          * 工作指针i从右向左不断扫描，找小于或者等于锚点元素的元素
          */
          while (i < right && a[i] <= pivot) {
              /*
              * 找到与锚点元素相等的元素将其交换到p所指示的位置
              */
              if (a[i] == pivot) {
                  swap(a, i, p);
                  p++;
              }
              i++;
          }
          /*
          * 工作指针j从左向右不断扫描，找大于或者等于锚点元素的元素
          */
          while (left <= j && a[j] >= pivot) {
              /*
              * 找到与锚点元素相等的元素将其交换到q所指示的位置
              */
              if (a[j] == pivot) {
                  swap(a, j, q);
                  q--;
              }
              j--;
          }
          /*
          * 如果两个工作指针i j相遇则一趟遍历结束
          */
          if (i >= j)
              break;

          /*
          * 将左边大于pivot的元素与右边小于pivot元素进行交换
          */
          swap(a, i, j);
          i++;
          j--;
      }
      /*
      * 因为工作指针i指向的是当前需要处理元素的下一个元素
      * 故而需要退回到当前元素的实际位置，然后将等于pivot元素交换到序列中间
      */
      i--;
      p--;
      while (p >= left) {
          swap(a, i, p);
          i--;
          p--;
      }
      /*
      * 因为工作指针j指向的是当前需要处理元素的上一个元素
      * 故而需要退回到当前元素的实际位置，然后将等于pivot元素交换到序列中间
      */
      j++;
      q++;
      while (q <= right) {
          swap(a, j, q);
          j++;
          q++;
      }

      /*
      * 递归遍历左右子序列
      */
      quickSort(a, left, i);
      quickSort(a, j, right);
  }
}
```