Keep2iron's Road to development

快速排序

算法描述

挑选基准值：从数列中挑出一个元素，称为“基准”（pivot），
分割：重新排序数列，所有比基准值小的元素摆放在基准前面，所有比基准值大的元素摆在基准后面（与基准值相等的数可以到任何一边）。在这- 个分割结束之后，对基准值的排序就已经完成，
递归排序子序列：递归地将小于基准值元素的子序列和大于基准值元素的子序列排序。

代码实现

/**
  * 快速排序（非递归版）
  */
private static void quickSortByNotRecursive(int[] arr) {
    Stack<Integer> stack = new Stack<>();
    stack.push(arr.length - 1);
    stack.push(0);

    while (!stack.isEmpty()) {
        Integer newStart = stack.pop();
        Integer newEnd = stack.pop();

        int partition = partition(arr, newStart, newEnd);
        if (newStart < partition - 1) {
            stack.push(partition - 1);
            stack.push(newStart);
        }
        if (partition + 1 < newEnd) {
            stack.push(newEnd);
            stack.push(partition + 1);
        }
    }
}

/**
  * 快速排序（递归版）
  */
private static void quickSortByRecursive(int[] arr, int start, int end) {
    if (start >= end) {
        return;
    }

    int partIndex = partition(arr, start, end);

    quickSortByRecursive(arr, start, partIndex - 1);
    quickSortByRecursive(arr, partIndex + 1, end);
}

/**
  * 分区算法
  */
private static int partition(int[] arr, int start, int end) {
    if (start < end) {
        int pivot = arr[start];
        while (start < end) {
            while (start < end && arr[end] >= pivot) end--;
            arr[start] = arr[end];
            while (start < end && arr[start] <= pivot) start++;
            arr[end] = arr[start];
        }

        arr[start] = pivot;
    }
    return start;
}

动图演示

维基百科-快速排序
 维基百科-归并排序
 cnblog-排序算法

希尔排序

算法描述

希尔排序，也称递减增量排序算法，是插入排序的一种更高效的改进版本。希尔排序是非稳定排序算法。

希尔排序是基于插入排序的以下两点性质而提出改进方法的：
插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率
但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位

步长的选择是希尔排序的重要部分。只要最终步长为1任何步长序列都可以工作。算法最开始以一定的步长进行排序。然后会继续以一定步长进行排序，最终算法以步长为1进行排序。当步长为1时，算法变为普通插入排序，这就保证了数据一定会被排序。

取初始的步长为step(初始值为数组长度arr的一半)
以步长为单位让arr[step] arr[step 2] … arr[step n]进行插入排序
步长进行除二直至步长单位为1时进行全数列的插入排序

代码实现

public void shellSort(int[] arr){
	int step = maxSize / 2;
	while (step >= 1) {
	    for (int i = step; i < arr.length; i += step) {
	        int currentItem = arr[i];
	        int preIndex = i - step;
	        while (preIndex >= 0 && arr[preIndex] > currentItem) {
	            arr[preIndex + step] = arr[preIndex];
	            preIndex -= step;
	        }
	        if (preIndex + step != i) {
	            arr[preIndex + step] = currentItem;
	        }
	    }
	    step /= 2;
	}
}

归并排序

算法描述

归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。

递归方案

申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
设定两个指针，最初位置分别为两个已经排序序列的起始位置
比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
重复步骤3直到某一指针到达序列尾
将另一序列剩下的所有元素直接复制到合并序列尾

代码实现

public static void mergeSort(int[] arr) {
    int[] result = new int[arr.length];

    mergeSortRecursive(arr, result, 0, arr.length - 1);
}

public static void mergeSortRecursive(int[] arr, int[] result, int start, int end) {
    if (start >= end) {
        return;
    }

    int length = end - start;
    int mid = start + (length >> 2);

    int start1 = start;
    int start2 = mid + 1;
    int end1 = mid;
    int end2 = end;

    mergeSortRecursive(arr, result, start1, end1);
    mergeSortRecursive(arr, result, start2, end2);

    int k = start;

    while (start1 <= end1 && start2 <= end2) {
        result[k++] = arr[start1] > arr[start2] ? arr[start2++] : arr[start1++];
    }
    while (start1 <= end1) {
        result[k++] = arr[start1++];
    }
    while (start2 <= end2) {
        result[k++] = arr[start2++];
    }

    for (int i = start; i <= end; i++) {
        arr[i] = result[i];
    }
}

大话Http

快速排序

快速排序

算法描述

代码实现

动图演示

希尔排序 & 归并排序

希尔排序

算法描述

代码实现

归并排序

算法描述

代码实现

动图演示