算法分类

比较排序

插入排序

简单插入排序

希尔排序

---

交换排序

冒泡排序

快速排序

---

选择排序

简单选择排序

堆排序

---

---

非比较排序

基数排序

桶排序

算法复杂度

稳定： 如果a原本在b前面，而a = b ,排序之后a仍然在前面

1. 插入排序

思想: 对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

1. 从第一个元素开始，该元素可以认为已经被排序；

2. 取出下一个元素，在已经排序的元素序列中从后向前扫描；

3. 如果该元素（已排序）大于新元素，将该元素移到下一位置；

4. 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；

5. 将新元素插入到该位置后；

6. 重复步骤2~5

public void insertSort(int[] a){
    for(int i = 1 ; i < a.length ; i++){
        int temp = a[i];
        int j = i ;
        while(j - 1 >= 0 && a[j-1] > temp){
            a[j] = a[j-1];
            j--;
        }
        a[j] = temp;
    }
}

2.希尔排序

思想:简单插入排序的改进版。它与插入排序的不同之处在于，它会优先比较距离较远的元素。希尔排序又叫缩小增量排序

1. 把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，

2. 当增量减至1时，整个数组恰好被分成一组

3. 增量的选取 从 数组长度的一半开始 ，每次减少一半

public void shellSort(int[] a){
    int step = a.length / 2;
    while(step >= 1){
        for(int i = step ; i < a.length ; i += step){
            int temp = a[i];
            int j = i;
            while(j - step >= 0 && a[j - step] > temp){
                a[j] = a[j-step];
                j -= step;
            }
            a[j] = temp;
        }
        step = step / 2;
    }
}

3.冒泡排序

思想:从第一个数开始，两两比较，大(小)的放后面，每一趟排序确定一个位置

• 优化:

  1. 设置一个标志flag，发生交换就置true，循环继续，如果一趟排序下来没有发生交换，即flag=false，则结束循环，排序完成

  2. 每一趟排序都确定了一个位置，所以每一趟比较的次数-1

public void bubbleSort(int[] a){
    for(int i = 0 ; i < a.length - 1 ; i++){
        boolean flag = true;
        for(int j = 0 ; j < a.length - 1 - i ; j++){
            if(a[j] > a[j+1]){
                flag = false;
                int temp = a[j];
                a[j] = a[j+1];
                a[j+1] = temp;
            }
        }
        if(flag) break;
    }
}

4.快速排序

思想: 通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。

1. 从数列中挑出一个元素，称为 “基准”（pivot）；

2. 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；

二路快排 将整个数组分成了小于v，大于v的两部分

• 从**下标i **这个位置向后扫描，
  • 当扫描的元素a小于v ：则继续向后扫描。
  • 当扫描的元素a大于v 停止扫描
• 从**下标j **这个位置向前扫描，
  • 当扫描的元素b大于v ：则继续向前扫描。
  • 当扫描的元素b小于v 停止扫描
• 如果 i < j 则交换对应元素，然后继续上述扫描

二路快排.png

public int partition(int[] a , int l , int r ){
    int pivot = a[l];
    int i = l+1 , j = r;
    while(true){
        while(i <= j && a[i] < pivot) i++;
        while(i <= j && a[j] > pivot) j--;
        if(i > j) break;
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
        i++;
        j--;
    }
    int temp = a[l];
    a[l] = a[j];
    a[j] = temp;
    return j;
}
public void quickSort(int[] a , int l , int r){
    if(l < r){
        int mid = partition(a,l,r);
        quickSort(a,l,mid-1);
        quickSort(a,mid+1 , r);
    }
}

二路排序只是提升了一下效率，当有大量重复值排序的时候，还是会沦为O(n^2)的排序算法,所以引入三路快排

三路快排 将数组分成了小于v，等于v，大于v的三个部分。遇到等于v的元素直接不用管，只需要处理小于v，大于v的元素就好了

需要两个变量lt,gt分别记录小于v的右边界 和 大于v的左边界

面要处理下标i 代表的元素a，分以下3种情况：

• a 等于v ：直接纳入绿色部分，即无需处理，下标i后移。
• a小于v ：将下标i的元素值和下标 lt+1（即等于v部分的第一个元素）交换，然后i下标后移，继而判断下一个元素；同时lt下标后移，代表小于v的元素新增了一个。
• a大于v ：同理，将下标i的元素值和下标 gt-1（大于v部分的前一个元素）交换，gt下标前移，代表大于v的元素新增了一个。注意此时下标i 无需后移，因为不同于小于v 部分，此时交换后的元素是未处理过的，所以要继续判断
  
  三路快排.png

public void quickSort(int[] a , int l , int r){
    if(l >= r) return;
    int pivot = a[l];
    int i = l+1 , lt = l , gt = r+1;
    while(i < gt){
        if(a[i] < pivot){
            swap(a,lt+1,i);
            lt++;
            i++;
        }else if(a[i] > pivot){
            swap(a,i,rt-1);
            gt--;
        }else i++;
    }
    swap(a,l,lt);
    quickSort(a,l,lt-1);
    quickSort(a,gt,r);
}
public void swap(int[] a , int i ,int j){
    int temp = a[i];
    a[i] = a[j];
    a[j] = temp;
}

关于pivot选取的优化

1. 随机选取数组中一个点

2. 三数取中 使用左端、右端和中心位置上的三个元素的中值作为pivot

应用 快速排序找第K大的数

如果k 在 lt，rt之间直接返回 ， 小于 lt 或 大于 rt递归查找