* @param left * @param right * @return */

public static int partition(int[] arr, int left, int right) { int pivotKey = arr[left];

while(left right) {

while(left = pivotKey) right --;

arr[left] = arr[right]; //把小的移动到左边 while(left pivotKey) left ++;

arr[right] = arr[left]; //把大的移动到右边 }

arr[left] = pivotKey; //最后把pivot赋值到中间 return left; }

/**

* 递归划分子序列 * @param arr * @param left * @param right */

public static void quickSort(int[] arr, int left, int right) { if(left >= right) return ;

int pivotPos = partition(arr, left, right); quickSort(arr, left, pivotPos-1); quickSort(arr, pivotPos+1, right); }

public static void sort(int[] arr) { if(arr == null || arr.length == 0) return ;

quickSort(arr, 0, arr.length-1); } }

总结快速排序的思想：冒泡+二分+递归分治，慢慢体会。。。

堆排序

堆排序是借助堆来实现的选择排序，思想同简单的选择排序，以下以大顶堆为例。注意：如果想升序排序就使用大顶堆，反之使用小顶堆。原因是堆顶元素需要交换到序列尾部。

首先，实现堆排序需要解决两个问题：

如何由一个无序序列键成一个堆？

如何在输出堆顶元素之后，调整剩余元素成为一个新的堆？ 第一个问题，可以直接使用线性数组来表示一个堆，由初始的无序序列建成一个堆就需要自底向上从第一个非叶元素开始挨个调整成一个堆。

第二个问题，怎么调整成堆？首先是将堆顶元素和最后一个元素交换。然后比较当前堆顶元素的左右孩子节点，因为除了当前的堆顶元素，左右孩子堆均满足条件，这时需要选择当前堆顶元素与左右孩子节点的较大者（大顶堆）交换，直至叶子节点。我们称这个自堆顶自叶子的调整成为筛选。

从一个无序序列建堆的过程就是一个反复筛选的过程。若将此序列看成是一个完全二叉树，则最后一个非终端节点是n/2取底个元素，由此筛选即可。举个栗子：

49,38,65,97,76,13,27,49序列的堆排序建初始堆和调整的过程如下：

实现代码： /**

*@Description:堆排序算法的实现，以大顶堆为例。 *@author 王旭 */

public class HeapSort {

/**

* 堆筛选，除了start之外，start~end均满足大顶堆的定义。 * 调整之后start~end称为一个大顶堆。 * @param arr 待调整数组 * @param start 起始指针 * @param end 结束指针 */

public static void heapAdjust(int[] arr, int start, int end) { int temp = arr[start];

for(int i=2*start+1; i) {

//左右孩子的节点分别为2*i+1,2*i+2

//选择出左右孩子较小的下标 if(i ]) { i ++; }

if(temp >= arr[i]) {

break; //已经为大顶堆，=保持稳定性。 }

arr[start] = arr[i]; //将子节点上移 start = i; //下一轮筛选 }

arr[start] = temp; //插入正确的位置 }

public static void heapSort(int[] arr) { if(arr == null || arr.length == 0) return ;

//建立大顶堆

for(int i=arr.length/2; i>=0; i--) { heapAdjust(arr, i, arr.length-1); }

for(int i=arr.length-1; i>=0; i--) { swap(arr, 0, i);

heapAdjust(arr, 0, i-1); }

}

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

arr[i] = arr[j]; arr[j] = temp; } }

希尔排序

希尔排序是插入排序的一种高效率的实现，也叫缩小增量排序。简单的插入排序中，如果待排序列是正序时，时间复杂度是O(n)，如果序列是基本有序的，使用直接插入排序效率就非常高。希尔排序就利用了这个特点。基本思想是：先将整个待排记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录基本有序时再对全体记录进行一次直接插入排序。

举个栗子：

从上述排序过程可见，希尔排序的特点是，子序列的构成不是简单的逐段分割，而是将某个相隔某个增量的记录组成一个子序列。如上面的例子，第一堂排序时的增量为5，第二趟排序的增量为3。由于前两趟的插入排序中记录的关键字是和同一子序列中的前一个记录的关键字进行比较，因此关键字较小的记录就不是一步一步地向前挪动，而是跳跃式地往前移，从而使得进行最后一趟排序时，整个序列已经做到基本有序，只要作记录的少量比较和移动即可。因此希尔排序的效率要比直接插入排序高。

希尔排序的分析是复杂的，时间复杂度是所取增量的函数，这涉及一些数学上的难题。但是在大量实验的基础上推出当n在某个范围内时，时间复杂度可以达到O(n^1.3)。

实现代码： /**

*@Description:希尔排序算法实现 *@author 王旭 */

public class ShellSort {

/**

* 希尔排序的一趟插入 * @param arr 待排数组 * @param d 增量 */

public static void shellInsert(int[] arr, int d) { for(int i=d; i) { int j = i - d;

int temp = arr[i]; //记录要插入的数据

while (j>=0 & arr[j]>temp) { //从后向前，找到比其小的数的位置 arr[j+d] = arr[j]; //向后挪动 j -= d; }

if (j != i - d) //存在比其小的数 arr[j+d] = temp;

} }

public static void shellSort(int[] arr) { if(arr == null || arr.length == 0) return ;

int d = arr.length / 2; while(d >= 1) {

shellInsert(arr, d); d /= 2; } } }

归并排序

归并排序是另一种不同的排序方法，因为归并排序使用了递归分治的思想，所以理解起来比较容易。其基本思想是，先递归划分子问题，然后合并结果。把待排序列看成由两个有序的子序列，然后合并两个子序列，然后把子序列看成由两个有序序列。。。。。倒着来看，其实就是先两两合并，然后四四合并。。。最终形成有序序列。空间复杂度为O(n)，时间复杂度为O(nlogn)。

举个栗子：