算法---排序
chenfei0 2020-04-15
排序过程详细的动态图可参考https://www.cnblogs.com/onepixel/articles/7674659.html
1.插入排序 稳定O(n^2)
稳定的意思是a=b，原本a在b前面，排序完成后a也在b前面。
插入排序的思路就是将数组逻辑上分成两段，一段是排好序的，一段是未排序的，每次从未排序的段中取出来一个，去排好序的里面找位置插入。
找的过程将排好序的那段位置进行移动，这样就一直有个位置可以放当前这个元素。
开始认为第一个元素是排好序的。
public static void insertSort(int[] arr) {
int length = arr.length;
for (int i = 1; i < length; i++) {
int data = arr[i];
for (int j = i - 1; j >= 0; j--) { //反向遍历比较
if (arr[j] > data) {
arr[j + 1] = arr[j]; //位置后移
arr[j] = data;
}
else {
break; // 前面都是排好序的，有一个比它小的，再前面肯定更小，直接可以跳出，不用再比较
}
}
}
}2.希尔排序 不稳定 n*log2n-O(n^2)
希尔排序其实是插入排序的一个改进版本，如上插入排序的代码，我们发现有一个break的操作。遇到前面已经排好序了。我们就不用再去遍历了。希尔排序就是增加这种有序段的数量。
希尔排序是按下标增量进行分组，对每一组进行插入排序，随着下标增量的减少，数组中有序段也越来越多。最后下标增量到1的时候便是整组排序了。
{1,5,8,9,6,3}
如果按下标增量2那么就是1,8,6一组进行排序，5,9,3 一组进行排序
第一次：{1,3,6,5,8,9}
...增量依次递减直到1
public static void shellSort(int[] arr) {
int len = arr.length;
//增量每次折半,最后增量为1的时候就是最后一次排序
for (int increment = len / 2; increment >= 1; increment /= 2) {
//类似插入排序
for (int i = increment; i < len; i++) { //按增量分开使用插入排序
int data = arr[i];
for (int j = i - increment; j >= 0 ; j -= increment) {
if (arr[j] > data) {
arr[j + increment] = arr[j]; //位置后移
arr[j] = data;
}
else {
break; // 前面都是排好序的，有一个比它小的，再前面肯定更小，直接可以跳出，不用再比较
}
}
}
}
}3.冒泡排序 稳定 O(n^2)
依次比较相邻两个元素大小，进行交换，每次就可以选择最大或者最小的。
/**
* 冒泡排序 稳定 依次比较相邻的两个元素大小，每轮结束就可以选出来一个最大或者最小的
* @param arr
*/
public static void bubbleSort(int[] arr) {
for (int i = 0; i < arr.length; i++) { //外层循环控制轮次
for (int j = 0; j < arr.length - 1 - i; j++) { //内层循环次数越来越少，因为内层跑完一次就找到一个数
if (arr[j] > arr[j+1]) { //交换位置
arr[j] = arr[j] + arr[j+1];
arr[j+1] = arr[j] - arr[j+1];
arr[j] = arr[j] - arr[j+1];
}
}
}
}4. 选择排序 不稳定 O(n^2)
有点类似插入排序会将数组分成两段，去未排序段中每次选择中最大或者最小的到另一段中。
比如从最左边开始，去依次遍历，找到最大或者最小的索引下标，然后交换位置。这样就找到了最大/最小的数。每轮只换一次位置，冒泡是每次比较都可能会换位置。
/**
* 选择排序 不稳定 先拿出一个数，去依次遍历，找到最大或者最小的。每轮换一次位置，冒泡是每次比较都可能会换位置。
* @param arr
*/
public static void selectionSort(int[] arr) {
int tempIndex;
for (int i = 0; i < arr.length; i++) {
tempIndex = i;
for (int j = i + 1; j < arr.length; j++) {
if (arr[j] < arr[tempIndex]) { //比较大小 记录下标位置
tempIndex = j;
}
}
if (tempIndex != i) { //交换位置
arr[i] = arr[i] + arr[tempIndex];
arr[tempIndex] = arr[i] - arr[tempIndex];
arr[i] = arr[i] - arr[tempIndex];
}
}
}5. 归并排序 稳定 O(nlogn)
归并排序是采用分治的思想，将要排序的数据拆分，再合并，过程如下图，合并的时候如下涂鸦线条，第一次红色线条，6和5比，5下去，左边的指针位置后移一位到9，第二次蓝色线条，6和9比，6下去，右边指针后移一位到8，第三次8和9比，8下去，最后剩下的9直接移下去。JDK的排序就是使用的归并排序java.util.Arrays#mergeSort()
代码
/**
* 归并排序 JDK源码java.util.Arrays#mergeSort()
* @param arr
* @param left
* @param right
*/
public static void mergeSort(int[] arr, int left, int right) {
if (left < right) {
int mid = (left + right) / 2;
mergeSort(arr, left, mid); //拆了之后的左
mergeSort(arr, mid + 1, right); //拆了之后的右
merge(arr, left, mid, right); //合并
}
}
/**
* 归并
*/
private static void merge(int[] arr, int left, int mid, int right) {
int[] arrTemp = new int[arr.length];
int leftPoint = left; //左边第一个下标
int rightPoint = mid + 1; //右边第一个下标
int currentPoint = left; //当前下标
//左右两边的数据对于自己来说都已经是有序的，所以就拿右边的依次和左边的进行大小比较，将对应的大小关系放入临时数组对应下标
//左边指针走到mid位置或者右边指针走到right位置，既结束循环，两边剩下的有序数据，直接追加在临时数组后面，先左后右
while (leftPoint <= mid && rightPoint <= right) {
if (arr[leftPoint] < arr[rightPoint]) {
arrTemp[currentPoint] = arr[leftPoint];
leftPoint++;
} else {
arrTemp[currentPoint] = arr[rightPoint];
rightPoint++;
}
currentPoint++;
}
//先处理左边剩下的直接放入对应位置
while (leftPoint <= mid) {
arrTemp[currentPoint++] = arr[leftPoint++];
}
//再处理右边剩下的
while (rightPoint <= right) {
arrTemp[currentPoint++] = arr[rightPoint++];
}
//将临时数组里面的数据放入原始数组中，注意只放merge的那一段的数据
for (int i = left; i <= right; i++) {
arr[i] = arrTemp[i];
}
}6.快速排序 不稳定 O(nlogn)
需要先选择一个基准数，一般选择第一个，和右边最后一个数据比较，如果比基准数小就交换位置，如果大则不交换，下标递减比较前一个，直到交换为止。然后切换成和左边第一个比较，如果比基准数大就换，否则下标递增继续判断，直到交换为止，然后切换到右边。。。就这样左右左右左右，直到碰到一起结束。次轮下来基准数左边是比它小的，右边是比它大的；将其左右的数据各自选一个基准数，执行一样的操作，如此反复，拆到最后就是一个有序的序列了。
如上图，最后分完就已经是一个排好的序列了，快排是边拆边排，归并是先拆，合并的时候再排。由上逻辑可以看出，快速排序中基准数的大小是至关重要的，最好的结果就是每次都取偏中间的数作为基准数。我们可以多随机选出来几个数，再从其中选一个出来作为基准数。和归并排序相比快排没有数据合并的过程，从下面的过程中也可以看出来快排就是之前递归里面说到的尾递归
/**
* 快速排序
* @param arr
*/
private static void quicklySort(int[] arr, int left, int right) {
int base = arr[left]; //我们选第一个作为基准数,也就是每次的进来left下标
int leftPoint = left; //左边找的位置
int rightPoint = right; //右边找的位置
while (leftPoint < rightPoint) { //左边指针小于右边 说明还没碰到一起
//从后往前找 如果后面的数大于等于基准数不交换，指针前移，需要的交换的时候跳出循环
while (leftPoint < rightPoint && arr[rightPoint] >= base) {
rightPoint--;
}
//上述循环跳出，并且左边指针小于右边指针 说明需要交换数据，左边因为换一个小的数据过去所以指针后移
if (leftPoint < rightPoint) {
int temp = arr[rightPoint];
arr[rightPoint] = arr[leftPoint];
arr[leftPoint] = temp;
leftPoint++;
}
//切换 从前往后找 如果左边的数小于等于基准数不交换，指针后移，需要的交换的时候跳出循环
while (leftPoint < rightPoint && arr[leftPoint] <= base) {
leftPoint++;
}
//上述循环跳出，并且左边指针小于右边指针 说明需要交换数据，右边因为换了一个大的数据过去所以指针前移
if (leftPoint < rightPoint) {
int temp = arr[rightPoint];
arr[rightPoint] = arr[leftPoint];
arr[leftPoint] = temp;
rightPoint--;
}
}
if (left < leftPoint) {
//左边
quicklySort(arr, left, leftPoint - 1);
}
if (leftPoint < right) {
//右边
quicklySort(arr, leftPoint + 1, right);
}
} 
相关推荐
要知道时间复杂度只是描述一个增长趋势，复杂度为O的排序算法执行时间不一定比复杂度为O长，因为在计算O时省略了系数、常数、低阶。实际上，在对小规模数据进行排序时，n2的值实际比 knlogn+c还要小。