排序算法
冒泡排序
冒泡排序是最简单的排序之一了，其大体思想就是通过与相邻元素的比较和交换来把小的数交换到最前面。这个过程类似于水泡向上升一样，因此而得名。
举个栗子：
对5,3,8,6,4这个无序序列进行冒泡排序。
1.首先从后向前冒泡，4和6比较，把4交换到前面，序列变成5,3,8,4,6。
2.同理4和8交换，变成5,3,4,8,6,3和4无需交换。
3.5和3交换，变成3,5,4,8,6,3.这样一次冒泡就完了，把最小的数3排到最前面了。
4.对剩下的序列依次冒泡就会得到一个有序序列。冒泡排序的时间复杂度为O(n^2)。
实现代码：
//冒泡排序，选择排序，
//从最左边开始 i=0
//比较第i个和第i+1个数字，如果arr[i]>arr[i+1],就将他们位置变化
//每一遍的结果，就是讲最大的移动到最后面
//如果比较一遍后，没有移动任何一个元素，就表明这个数组已经有序
public static void bobSort(int[] arr) {
boolean flag = true;
int a = arr.length - 1;
while (flag) {
flag = false;
for (int i = 0; i < a; i++) {
if (arr[i] > arr[i + 1]) {
int ch = arr[i];
arr[i] = arr[i + 1];
arr[i + 1] = ch;
flag = true;
}
}
a--;
}
}
选择排序
选择排序的思想其实和冒泡排序有点类似，都是在一次排序后把最小的元素放到最前面。但是过程不同，冒泡排序是通过相邻的比较和交换。而选择排序是通过对整体的选择。
举个栗子:
对5,3,8,6,4这个无序序列进行简单选择排序，
1.首先要选择5以外的最小数来和5交换，也就是选择3和5交换，一次排序后就变成了3,5,8,6,4.
2.对剩下的序列一次进行选择和交换，最终就会得到一个有序序列。
3.其实选择排序可以看成冒泡排序的优化，因为其目的相同，只是选择排序只有在确定了最小数的前提下才进行交换，大大减少了交换的次数。选择排序的时间复杂度为O(n^2)。
实现代码：
// 选择排序
// 从arr[i]后面选一个最小的，和arr[i]替换位置
public static void selectSort(int[] arr) {
int flag = 0;
int index = 0;
while (index < arr.length) {
for (int i = arr.length - 1; i > index; i--) {
if (arr[flag] > arr[i]) {
flag = i;
}
}
int a = arr[flag];
arr[flag] = arr[index];
arr[index] = a;
index++;
flag = index;
}
}
插入排序
插入排序不是通过交换位置而是通过比较找到合适的位置插入元素来达到排序的目的的。
相信大家都有过打扑克牌的经历，特别是牌数较大的。在分牌时可能要整理自己的牌，牌多的时候怎么整理呢？就是拿到一张牌，找到一个合适的位置插入。这个原理其实和插入排序是一样的。
举个栗子:
对5,3,8,6,4这个无序序列进行简单插入排序，
1.首先假设第一个数的位置时正确的，想一下在拿到第一张牌的时候，没必要整理。
2.然后3要插到5前面，把5后移一位，变成3,5,8,6,4.想一下整理牌的时候应该也是这样吧。
3.然后8不用动，6插在8前面，8后移一位，4插在5前面，从5开始都向后移一位。
4.注意在插入一个数的时候要保证这个数前面的数已经有序。简单插入排序的时间复杂度也是O(n^2)。
实现代码：
// 插入排序
// 前面i个已经是有序的了，把第i+1个插入到前面i个里面合适的位置
public static void insetSort(int[] arr) {
int index = 0;
while (index < arr.length-1) {
for (int i = 0; i <= index; i++) {
if (arr[i] < arr[index + 1] && arr[i + 1] >= arr[index + 1]) {
moveArr(arr, index + 1, i+1);
}
}
index++;
}
}
// 插入排序所需要的移动方法
private static void moveArr(int[] arr, int start, int end) {
int a = arr[start];
for (int i = start; i > end; i--) {
arr[i] = arr[i - 1];
}
arr[end] = a;
}
快速排序
快速排序一听名字就觉得很高端，在实际应用当中快速排序确实也是表现最好的排序算法。
快速排序虽然高端，但其实其思想是来自冒泡排序，冒泡排序是通过相邻元素的比较和交换把最小的冒泡到最顶端，而快速排序是比较和交换小数和大数，这样一来不仅把小数冒泡到上面同时也把大数沉到下面。
举个栗子：
对5,3,8,6,4这个无序序列进行快速排序，思路是右指针找比基准数小的，左指针找比基准数大的，交换之。
- 5,3,8,6,4 用5作为比较的基准，最终会把5小的移动到5的左边，比5大的移动到5的右边。
- 5,3,8,6,4 首先设置i,j两个指针分别指向两端，j指针先扫描（思考一下为什么？）4比5小停止。然后i扫描，8比5大停止。交换i,j位置。
- 5,3,4,6,8 然后j指针再扫描，这时j扫描4时两指针相遇。停止。然后交换4和基准数。
- 4,3,5,6,8 一次划分后达到了左边比5小，右边比5大的目的。之后对左右子序列递归排序，最终得到有序序列。
上面留下来了一个问题：为什么一定要j指针先动呢？首先这也不是绝对的，这取决于基准数的位置，因为在最后两个指针相遇的时候，要交换基准数到相遇的位置。一般选取第一个数作为基准数，那么就是在左边，所以最后相遇的数要和基准数交换，那么相遇的数一定要比基准数小。所以j指针先移动才能先找到比基准数小的数。
快速排序是不稳定的，其时间平均时间复杂度是O(nlgn)。
实现代码：
其实上面的代码还可以再优化，上面代码中基准数已经在pivotKey中保存了，所以不需要每次交换都设置一个temp变量，在交换左右指针的时候只需要先后覆盖就可以了。这样既能减少空间的使用还能降低赋值运算的次数。优化代码如下：
//快速排序
//以第i个为基准，从最右边起，找到比arr[i]小的，标记arr[min],找到。从第i个起，找到比arr[i]大的，标记为arr[max],交换max和min
//然后继续，直到下表max=min，然后把arr[i]和arr[max/min],交换。
//此刻，数组以arr[max/min],为界限，左边比他小，右边比他大，
//然后将这两边，继续执行这样的操作
//进行一次划分
public static int partition (int[] arr , int left, int right) {
// TODO Auto-generated method stub
int pivotKey = arr[left];
int pivotPointer = left;
while (left < right) {
while(arr[right] > pivotKey && left < right) {
right--;
}
while (arr[left] <= pivotKey && left < right) {
left++;
}
swap(arr, left, right);//交换位置
}
swap(arr, pivotPointer, left);
return left;
}
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);
}
总结快速排序的思想：冒泡+二分+递归分治，慢慢体会。。。
堆排序
堆排序是借助堆来实现的选择排序，思想同简单的选择排序，以下以大顶堆为例。注意：如果想升序排序就使用大顶堆，反之使用小顶堆。原因是堆顶元素需要交换到序列尾部。
首先，实现堆排序需要解决两个问题：
- 如何由一个无序序列键成一个堆？
- 如何在输出堆顶元素之后，调整剩余元素成为一个新的堆？
第一个问题，可以直接使用线性数组来表示一个堆，由初始的无序序列建成一个堆就需要自底向上从第一个非叶元素开始挨个调整成一个堆。
第二个问题，怎么调整成堆？首先是将堆顶元素和最后一个元素交换。然后比较当前堆顶元素的左右孩子节点，因为除了当前的堆顶元素，左右孩子堆均满足条件，这时需要选择当前堆顶元素与左右孩子节点的较大者（大顶堆）交换，直至叶子节点。我们称这个自堆顶自叶子的调整成为筛选。
从一个无序序列建堆的过程就是一个反复筛选的过程。若将此序列看成是一个完全二叉树，则最后一个非终端节点是n/2取底个元素，由此筛选即可。
举个栗子：
49,38,65,97,76,13,27,49序列的堆排序建初始堆和调整的过程如下：
实现代码：
希尔排序
希尔排序是插入排序的一种高效率的实现，也叫缩小增量排序。简单的插入排序中，如果待排序列是正序时，时间复杂度是O(n)，如果序列是基本有序的，使用直接插入排序效率就非常高。希尔排序就利用了这个特点。基本思想是：先将整个待排记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录基本有序时再对全体记录进行一次直接插入排序。
举个栗子：
从上述排序过程可见，希尔排序的特点是，子序列的构成不是简单的逐段分割，而是将某个相隔某个增量的记录组成一个子序列。
如上面的例子，第一堂排序时的增量为5，第二趟排序的增量为3。由于前两趟的插入排序中记录的关键字是和同一子序列中的前一个记录的关键字进行比较，因此关键字较小的记录就不是一步一步地向前挪动，而是跳跃式地往前移，从而使得进行最后一趟排序时，整个序列已经做到基本有序，只要作记录的少量比较和移动即可。因此希尔排序的效率要比直接插入排序高。
希尔排序的分析是复杂的，时间复杂度是所取增量的函数，这涉及一些数学上的难题。但是在大量实验的基础上推出当n在某个范围内时，时间复杂度可以达到O(n^1.3)。
实现代码：
/**
*希尔排序，类似不同步长的选择排序
* @param args
*/
public static void shellSort(int[] arr) {
int dk = arr.length/2;
while (dk>=1) {
System.out.printf("dk=%d",dk);
System.out.println();
shellInsertSort(arr, dk);
dk = dk/2;
}
}
//一次希尔排序
public static void shellInsertSort(int[] arr, int dk) {
for (int i = dk; i < arr.length; i++) {//从后面往前插入
if(arr[i] < arr[i-dk]) {
int j;
int x = arr[i];
arr[i] = arr[i-dk];
for(j = i-dk;j>=0&&x<arr[j];j = j-dk) {
arr[j+dk] = arr[j];
}
arr[j+dk] = x;
}
}
}
归并排序
归并排序是另一种不同的排序方法，因为归并排序使用了递归分治的思想，所以理解起来比较容易。
其基本思想是，先递归划分子问题，然后合并结果。把待排序列看成由两个有序的子序列，然后合并两个子序列，然后把子序列看成由两个有序序列。。。。。倒着来看，其实就是先两两合并，然后四四合并。。。最终形成有序序列。空间复杂度为O(n)，时间复杂度为O(nlogn)。
举个栗子：
实现代码：
/**
* 合并两个有序数组
* @param arr 待合并数组
* @param left 左指针
* @param mid 中间指针
* @param right 右指针
*/
public static void merge(int[] arr, int left, int mid, int right) {
int[] temp = new int[right-left+1];//中间过度数组
int index1 = left;//遍历其中一个数组
int index2 = mid+1;//遍历另外一个数组，因为mid可能等于left,遍历的时候，不能左右数组都拥有mid这个数组值。
int index = 0;//中间数组temp的下标
while(index1 <= mid && index2 <= right) {
if(arr[index1]>arr[index2]) {
temp[index] = arr[index2];
index2++;
}else {
temp[index] = arr[index1];
index1++;
}
index++;
}
while(index1 <= mid) {//把第一个数组剩余没有插入的直接插入
temp[index] = arr[index1];
index++;
index1++;
}
while(index2 <= right) {//把第二个剩余没有插入的直接插入
temp[index] = arr[index2];
index++;
index2++;
}
//覆盖原来的数组
for (int i = 0; i < temp.length; i++) {
arr[left+i] = temp[i];
}
}
计数排序
如果在面试中有面试官要求你写一个O(n)时间复杂度的排序算法，你千万不要立刻说：这不可能！虽然前面基于比较的排序的下限是O(nlogn)。但是确实也有线性时间复杂度的排序，只不过有前提条件，就是待排序的数要满足一定的范围的整数，而且计数排序需要比较多的辅助空间。其基本思想是，用待排序的数作为计数数组的下标，统计每个数字的个数。然后依次输出即可得到有序序列。
实现代码：
/*
* 计数排序
* 用待排序的数作为计数数组的下标，统计每个数字的个数。然后依次输出即可得到有序序列。
*/
public static void CountSort(int[] arr) {
if(arr.length == 0 || arr == null) {
return;
}
int maxsize = maxSize(arr);
int[] tmp = new int[maxsize+1];
for (int i = 0; i < arr.length; i++) {
tmp[arr[i]]++;
}
//将记录好的数据，再放回arr数组中
int index = 0;
for (int i = 0; i < tmp.length; i++) {
for (int j = 1; j <= tmp[i]; j++) {//改坐标下的数组，记录了几次，就循环输出几次
arr[index] = i;
index++;
}
}
}
public static int maxSize(int[] arr) {
int flag = 0;
for (int i = 0; i < arr.length; i++) {
if(arr[i]>arr[flag]) {
flag = i;
}
}
return arr[flag];
}
桶排序
桶排序算是计数排序的一种改进和推广，但是网上有许多资料把计数排序和桶排序混为一谈。其实桶排序要比计数排序复杂许多。
对桶排序的分析和解释借鉴这位兄弟的文章（有改动）：http://hxraid.iteye.com/blog/647759
桶排序的基本思想：
假设有一组长度为N的待排关键字序列K[1….n]。首先将这个序列划分成M个的子区间(桶) 。然后基于某种映射函数 ，将待排序列的关键字k映射到第i个桶中(即桶数组B的下标 i) ，那么该关键字k就作为B[i]中的元素(每个桶B[i]都是一组大小为N/M的序列)。接着对每个桶B[i]中的所有元素进行比较排序(可以使用快排)。然后依次枚举输出B[0]….B[M]中的全部内容即是一个有序序列。bindex=f(key) 其中，bindex 为桶数组B的下标(即第bindex个桶), k为待排序列的关键字。桶排序之所以能够高效，其关键在于这个映射函数，它必须做到：如果关键字k1
举个栗子：
假如待排序列K= {49、 38 、 35、 97 、 76、 73 、 27、 49 }。这些数据全部在1—100之间。因此我们定制10个桶，然后确定映射函数f(k)=k/10。则第一个关键字49将定位到第4个桶中(49/10=4)。依次将所有关键字全部堆入桶中，并在每个非空的桶中进行快速排序后得到如图所示。只要顺序输出每个B[i]中的数据就可以得到有序序列了。
桶排序分析：
桶排序利用函数的映射关系，减少了几乎所有的比较工作。实际上，桶排序的f(k)值的计算，其作用就相当于快排中划分，希尔排序中的子序列，归并排序中的子问题，已经把大量数据分割成了基本有序的数据块(桶)。然后只需要对桶中的少量数据做先进的比较排序即可。
对N个关键字进行桶排序的时间复杂度分为两个部分：
(1) 循环计算每个关键字的桶映射函数，这个时间复杂度是O(N)。
(2) 利用先进的比较排序算法对每个桶内的所有数据进行排序，其时间复杂度为 ∑ O(Ni*logNi) 。其中Ni 为第i个桶的数据量。
很显然，第(2)部分是桶排序性能好坏的决定因素。尽量减少桶内数据的数量是提高效率的唯一办法(因为基于比较排序的最好平均时间复杂度只能达到O(N*logN)了)。因此，我们需要尽量做到下面两点：
(1) 映射函数f(k)能够将N个数据平均的分配到M个桶中，这样每个桶就有[N/M]个数据量。
(2) 尽量的增大桶的数量。极限情况下每个桶只能得到一个数据，这样就完全避开了桶内数据的“比较”排序操作。当然，做到这一点很不容易，数据量巨大的情况下，f(k)函数会使得桶集合的数量巨大，空间浪费严重。这就是一个时间代价和空间代价的权衡问题了。
对于N个待排数据，M个桶，平均每个桶[N/M]个数据的桶排序平均时间复杂度为：
O(N)+O(M(N/M)log(N/M))=O(N+N(logN-logM))=O(N+NlogN-N*logM)
当N=M时，即极限情况下每个桶只有一个数据时。桶排序的最好效率能够达到O(N)。
总结：
桶排序的平均时间复杂度为线性的O(N+C)，其中C=N*(logN-logM)。如果相对于同样的N，桶数量M越大，其效率越高，最好的时间复杂度达到O(N)。 当然桶排序的空间复杂度 为O(N+M)，如果输入数据非常庞大，而桶的数量也非常多，则空间代价无疑是昂贵的。此外，桶排序是稳定的。
实现代码：
/**
* 桶排序
* @param arr
* @return
*/
public static void bucketSort(int[] arr) {
if(arr == null|| arr.length==0) {
return;
}
ArrayList<LinkedList> arrayList = new ArrayList<LinkedList>();//方便移动数据，使用linkList装数据
for (int i = 0; i < arr.length/10; i++) {
arrayList.add(new LinkedList<Integer>());
}
for (int i = 0; i < arr.length; i++) {//开始桶排序
int index = arr[i]/10;
arrayList.get(index).add(arr[i]);
}
//上面只是把数据放到同样的桶里面了，但是不一定是排好序的，需要排一下需
//可以自己手写排序，也可以使用Collection进行排序
for (LinkedList<Integer> linkedList : arrayList) {
Collections.sort(linkedList);
}
//开始获取桶里面的数据，放到arr原始的数组中
int index = 0;
for (LinkedList<Integer> linkedList : arrayList) {
for (int i = 0; i < linkedList.size(); i++) {
arr[index++] = linkedList.get(i);
}
}
}
基数排序
基数排序又是一种和前面排序方式不同的排序方式，基数排序不需要进行记录关键字之间的比较。
基数排序是一种借助多关键字排序思想对单逻辑关键字进行排序的方法。所谓的多关键字排序就是有多个优先级不同的关键字。
比如说成绩的排序，如果两个人总分相同，则语文高的排在前面，语文成绩也相同则数学高的排在前面。。。如果对数字进行排序，那么个位、十位、百位就是不同优先级的关键字，如果要进行升序排序，那么个位、十位、百位优先级一次增加。基数排序是通过多次的收分配和收集来实现的，关键字优先级低的先进行分配和收集。
举个栗子：
实现代码：
/**
* 基数排序
* @param args
*/
public static void radixSort(int[] arr) {
ArrayList<ArrayList<Integer>> arrayList = new ArrayList<ArrayList<Integer>>();
for (int i = 0; i < 10; i++) {//由于需要多次对基数进行调整，所以每次都需要清理一下基数，否则会有脏数据
arrayList.add(new ArrayList<Integer>());
}
int step = 1;
int array0Size = arrayList.get(0).size();
while(array0Size < arr.length) { //基数第一个装了全部数据之后，表示已经有序
System.out.println("arrayList.size="+arrayList.get(0).size()+",arr.length="+arr.length);
for (int i = 0; i < arr.length; i++) {
int index = (arr[i]/step)%10;
arrayList.get(index).add(arr[i]);
}
copy(arr,arrayList);
System.out.println("step = "+step);
step = step*10;
array0Size = arrayList.get(0).size();
arrayList.clear();
for (int i = 0; i < 10; i++) {//由于需要多次对基数进行调整，所以每次都需要清理一下基数，否则会有脏数据
arrayList.add(new ArrayList<Integer>());
}
}
}
//读出，并覆盖元素组
public static void copy(int[] arr, ArrayList<ArrayList<Integer>> arrayList) {
int index = 0;
for (ArrayList arrayList2 : arrayList) {
System.out.println(arrayList2);
for (int i = 0; i < arrayList2.size(); i++) {
arr[index] = (int) arrayList2.get(i);
index++;
}
}
}
堆排序（性能很不错）
大顶堆：
父节点大于左右子节点，左右子节点不进行大小比较
小顶堆：
父节点小于左右子节点，左右子节点不做比较。
思路：
通过大顶堆或者小顶堆的思路将数组进行排序（这里的堆，指的是一个完全二叉树，在数组中，完全二叉树的父节点和左右叶子结点的关系为：父节点为n，左子节点为2n+1，又子节点为2n+2）。
大顶堆：arr[i] >= arr[2i+1] && arr[i] >= arr[2i+2]
小顶堆：arr[i] <= arr[2i+1] && arr[i] <= arr[2i+2]
如下图：
步骤一 构造初始堆。将给定无序序列构造成一个大顶堆（一般升序采用大顶堆，降序采用小顶堆)。
a.假设给定无序序列结构如下
2.此时我们从最后一个非叶子结点开始（叶结点自然不用调整，第一个非叶子结点 arr.length/2-1=5/2-1=1，也就是下面的6结点），从左至右，从下至上进行调整。
4.找到第二个非叶节点4，由于[4,9,8]中9元素最大，4和9交换。
这时，交换导致了子根[4,5,6]结构混乱，继续调整，[4,5,6]中6最大，交换4和6。
此时，我们就将一个无需序列构造成了一个大顶堆。
步骤二 将堆顶元素与末尾元素进行交换，使末尾元素最大。然后继续调整堆，再将堆顶元素与末尾元素交换，得到第二大元素。如此反复进行交换、重建、交换。
a.将堆顶元素9和末尾元素4进行交换
b.重新调整结构，使其继续满足堆定义
c.再将堆顶元素8与末尾元素5进行交换，得到第二大元素8.
后续过程，继续进行调整，交换，如此反复进行，最终使得整个序列有序
再简单总结下堆排序的基本思路：
a.将无需序列构建成一个堆，根据升序降序需求选择大顶堆或小顶堆;
b.将堆顶元素与末尾元素交换，将最大元素"沉"到数组末端;
c.重新调整结构，使其满足堆定义，然后继续交换堆顶元素与当前末尾元素，反复执行调整+交换步骤，直到整个序列有序。
代码实现：
/**
* 堆排序
*
* @author zhanbei
*
*/
public class HeapSort {
public static void main(String[] arg) {
// TODO Auto-generated method stub
int[] arr = { 4, 6, 8, 5, 9 };
heapSort(arr);
System.out.println("排序后的arr = " + Arrays.toString(arr));
}
// 编写一个堆排序
public static void heapSort(int[] arr) {
System.out.println("开始堆排序");
int temp = 0;// 每次堆排序后，把堆顶元素保存到数组后，用于交换
// 开始构建大顶堆，
for (int i = arr.length / 2 - 1; i >= 0; i--) {
adjustHeap(arr, i, arr.length);
}
// 将堆顶元素沉淀到末端
// 调整结构，继续排序
// 再次沉淀
for (int j = arr.length - 1; j > 0; j--) {
System.out.println("j = " + j);
temp = arr[j];
arr[j] = arr[0];
arr[0] = temp;
adjustHeap(arr, 0, j);
}
}
// 将一个数组调整为大顶堆
/**
* 1、比较该父节点下的左右子节点 2、左右子节点较大的和父节点比较 3、将父节点和较大子节点交换，同时下标交换，便于后期继续比较
*/
/**
*
* @param arr 待调整的数组
* @param i 标识叶子结点在数组中的额索引
* @param length 对少个元素进行调整，length在逐渐减少
*/
public static void adjustHeap(int arr[], int i, int length) {
int temp = arr[i];
for (int k = 2 * i + 1; k < length; k = k * 2 + 1) {
if (k+1 < length && arr[k] < arr[k + 1]) { // 比较左右子节点大小
k++;// 选大的
}
if (arr[k] > temp) {// 比较父节点和大的子节点的大小
arr[i] = arr[k];// 交换大的到父节点
i = k;// 交换下表
} else {
break;
}
arr[i] = temp;// 将父节点的值交换下来。
}
}
}
总结:
在前面的介绍和分析中我们提到了冒泡排序、选择排序、插入排序三种简单的排序及其变种快速排序、堆排序、希尔排序三种比较高效的排序。后面我们又分析了基于分治递归思想的归并排序还有计数排序、桶排序、基数排序三种线性排序。我们可以知道排序算法要么简单有效，要么是利用简单排序的特点加以改进，要么是以空间换取时间在特定情况下的高效排序。但是这些排序方法都不是固定不变的，需要结合具体的需求和场景来选择甚至组合使用。才能达到高效稳定的目的。没有最好的排序，只有最适合的排序。
下面就总结一下排序算法的各自的使用场景和适用场合。
- 从平均时间来看，快速排序是效率最高的，但快速排序在最坏情况下的时间性能不如堆排序和归并排序。而后者相比较的结果是，在n较大时归并排序使用时间较少，但使用辅助空间较多。
- 上面说的简单排序包括除希尔排序之外的所有冒泡排序、插入排序、简单选择排序。其中直接插入排序最简单，但序列基本有序或者n较小时，直接插入排序是好的方法，因此常将它和其他的排序方法，如快速排序、归并排序等结合在一起使用。
- 基数排序的时间复杂度也可以写成O(d*n)。因此它最使用于n值很大而关键字较小的的序列。若关键字也很大，而序列中大多数记录的最高关键字均不同，则亦可先按最高关键字不同，将序列分成若干小的子序列，而后进行直接插入排序。
- 从方法的稳定性来比较，基数排序是稳定的内排方法，所有时间复杂度为O(n^2)的简单排序也是稳定的。但是快速排序、堆排序、希尔排序等时间性能较好的排序方法都是不稳定的。稳定性需要根据具体需求选择。
- 上面的算法实现大多数是使用线性存储结构，像插入排序这种算法用链表实现更好，省去了移动元素的时间。具体的存储结构在具体的实现版本中也是不同的。
附：基于比较排序算法时间下限为O(nlogn)的证明：
基于比较排序下限的证明是通过决策树证明的，决策树的高度Ω（nlgn），这样就得出了比较排序的下限。
首先要引入决策树。 首先决策树是一颗二叉树，每个节点表示元素之间一组可能的排序，它予以京进行的比较相一致，比较的结果是树的边。 先来说明一些二叉树的性质，令T是深度为d的二叉树，则T最多有2^片树叶。 具有L片树叶的二叉树的深度至少是logL。 所以，对n个元素排序的决策树必然有n!片树叶（因为n个数有n!种不同的大小关系），所以决策树的深度至少是log(n!)，即至少需要log(n!)次比较。 而 log(n!)=logn+log(n-1)+log(n-2)+…+log2+log1 >=logn+log(n-1)+log(n-2)+…+log(n/2) >=(n/2)log(n/2) >=(n/2)logn-n/2 =O(nlogn) 所以只用到比较的排序算法最低时间复杂度是O(nlogn)。
查找算法
二分查找
前提：已经有序的数组，通过递归或者伪递归的方式进行查找，通过和数组中间数对比，如果不是，就根据大小，采取决策，向右递归或者左递归继续二分查找
实现代码：
/**
* 二分查找，前提：有序
*
* @param arr 需要排序数组
* @param start 开始下表
* @param end 结束下表
* @param target 要查找的数字
*/
public static int binarySearch(int[] arr, int start, int end, int target) {
if(start>end) {
return -1;
}
int flag = (start + end) / 2;
if (arr[flag] == target) {
return flag;
}
if (arr[flag] > target) {
return binarySearch(arr, start, flag-1, target);
}
if (arr[flag] < target) {
return binarySearch(arr, flag+1, end, target);
}
return -1;
}
插值查找算法
- 插值查找原理介绍:
插值查找算法类似于二分查找，不同的是插值查找每次从自适应mid处开始查找。
- 将折半查找中的求mid索引的公式，low表示左边索引left, high表示右边索引right.
key就是前面我们讲的findVal
- int mid = low + (high - low) * (key - arr[low])/ (arr[high]- arr[low]) ;/插值索引/
对应前面的代码公式:
int mid= left+ (right - left) * (findVal - arr[left])/ (arr[right] - arr[left])
备注：主要判断mid是否数组越界
斐波那契（换金分割）查找算法
1)黄金分割点是指把一条线段分割为两部分，使其中-部分与 全长之比等于另- -部分 与这部分之比。取其前三位，数字的近似值是0.618。由于按此比例设计的造型十分美丽，因此称为黄金分割，也称为中外比。这是一个神奇的数字，会带来意向不大的效果。
2)斐波那契数列 {1,1,2,3,5, 8, 13,21,34,55 }发现斐波那契数列的两个相邻数的比例，无限接近黄金分割值
斐波那契查找原理
斐波那契查找原理与前两种相似，仅仅改变了中间结点(mid)的位置，mid不再是中间或插值得到，而是位置，于黄金分割点附近，即mid=low+F(k-1)-1 (F代表斐波那契数列)，如下图所示
➢对F(k-1)-1的理解:
- 由斐波那契数列F[k]=F[k-1]+F[k-2] 的性质，可以得到(F[k]-1) = (F[k-1]-1) + (F[k-2]-1) +1。该式说明:只要顺序表的长度为F[k]-1,则可以将该表分成长度为F[k-1]-1和F[k<-2]-1的两段，即如上图所示。从而中间位置为mid=low+F(k-1)-1
2)类似的， 每一.子段也可以用相同的方式分割
3)但顺序表长度n 不一定刚好等于F[k]-1,所以需要将原来的顺序表长度n增加至F[k]-1。这里的k值只要能使得F[k]-1恰好大于或等于n即可，由以下代码得到,顺序表长度增加后，新增的位置(从n+1到F[k]-1位置)，都赋为n位置的值即可。while(n> fb(k)-1) k++;
代码实现：
/**
* 产生一个斐波那契数列
* @param maxSize 数列对大长度
* @return 如果不存在，就直接返回-1，如果存在，返回下表
*/
private static int[] fib(int maxSize) {
int[] f = new int[maxSize];
f[0] = 1;
f[1] = 1;
for (int i = 2; i < maxSize; i++) {
f[i] = f[i-1] + f[i-2];
}
return f;
}
public static int fibSearch(int[] arr , int key) {
int low = 0;
int hight = arr.length-1;
int k = 0;//标识斐波那契分割数值的下表
int mid = 0 ;
int[] f = fib(arr.length);
//获取斐波那契分割数组下表
while (hight > f[k] - 1) {
k++;
}
//因为f[k]值可能大于arr的长度，我们使用arrays类，构造一个新的数组，并指向arr[]
int[] tmp = Arrays.copyOf(arr, f[k]);
//补齐新构造的数组的后几位
for(int i = hight+1;i<tmp.length;i++) {
tmp[i] = arr[hight];
}
while (hight>=low) {
mid=low+f[k-1]-1;
if(arr[mid] > key) {
hight = mid-1;
k--;
}else if(arr[mid] < key) {
low = mid+1;
k-=2;
}else {
if(mid<=hight) {
return mid;
}else {
return hight;
}
}
}
return -1;
}
哈希表
代码实现：
//雇员信息
class Emp {
public int id;
public String name;
public Emp nextEmp;
public int getId() {
return id;
}
public void setId(int id) {
this.id = id;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public Emp getNextEmp() {
return nextEmp;
}
public void setNextEmp(Emp nextEmp) {
this.nextEmp = nextEmp;
}
}
//哈希表中的链表头结点
class EmpLinkedList {
Emp head = null;
}
//哈希表
class HashTab {
EmpLinkedList[] empLinkedListsArr;
public HashTab(int size) {
empLinkedListsArr = new EmpLinkedList[size];
}
public void addEmp(Emp emp) {
int flag = emp.id % empLinkedListsArr.length;
Emp empFlag = empLinkedListsArr[flag].head;
while (Optional.ofNullable(empFlag).map(Emp::getNextEmp) != null) {
if (empFlag.getNextEmp().getId() > emp.id) {// 从小到大排序
emp.nextEmp = empFlag.nextEmp;
empFlag.nextEmp = emp;
}
}
}
public Emp get(int id) {
int flag = id % empLinkedListsArr.length;
Emp empFlag = empLinkedListsArr[flag].head;
while (Optional.ofNullable(empFlag).map(Emp::getNextEmp) != null) {
if(empFlag.id == id) {
return empFlag;
}
}
return null;
}
//.................
}
树结构
二叉树
各种树定义
满二叉树：一棵有n层的二叉树，除第n层外，每层都有两个子节点，那么这棵树就是满二叉树。
完全二叉树：
完全二叉树由满二叉树引进而来。假设二叉树有h层，除第h层外，其他各层的节点数均已达到最大个数（1至h-1层为满二叉树），第h层所有的节点都集中在最左边，这棵树就是完全二叉树。
另见：https://www.jianshu.com/p/683ccf7b4712
遍历(前序遍历，中序遍历，后序遍历)：
前序遍历：
- 先输出当前节点
- 如果左子树点不为空，则递归继续前序遍历
- 如果右子树节点不为空，则递归继续前序遍历
中序遍历：
- 如果当前节点左子树不为空，则递归中序遍历
- 输出当前节点
- 如果当前节点右子树不为空，则递归中序遍历
后序遍历：
- 如果当前节点左子树不为空，递归后序遍历
- 如果当前节点右子树不为空，递归后序遍历
- 输出输出当前节点
二叉树查找指定节点
使用中序，前序，后序遍历进行查找
代码实现：
//先创建HeroNode 结点
class HeroNode {
private int no;
private String name;
private HeroNode left; //默认null
private HeroNode right; //默认null
public HeroNode(int no, String name) {
this.no = no;
this.name = name;
}
public int getNo() {
return no;
}
public void setNo(int no) {
this.no = no;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public HeroNode getLeft() {
return left;
}
public void setLeft(HeroNode left) {
this.left = left;
}
public HeroNode getRight() {
return right;
}
public void setRight(HeroNode right) {
this.right = right;
}
@Override
public String toString() {
return "HeroNode [no=" + no + ", name=" + name + "]";
}
//递归删除结点
//1.如果删除的节点是叶子节点，则删除该节点
//2.如果删除的节点是非叶子节点，则删除该子树
public void delNode(int no) {
//思路
/*
* 1. 因为我们的二叉树是单向的，所以我们是判断当前结点的子结点是否需要删除结点，而不能去判断当前这个结点是不是需要删除结点.
2. 如果当前结点的左子结点不为空，并且左子结点 就是要删除结点，就将this.left = null; 并且就返回(结束递归删除)
3. 如果当前结点的右子结点不为空，并且右子结点 就是要删除结点，就将this.right= null ;并且就返回(结束递归删除)
4. 如果第2和第3步没有删除结点，那么我们就需要向左子树进行递归删除
5. 如果第4步也没有删除结点，则应当向右子树进行递归删除.
*/
//2. 如果当前结点的左子结点不为空，并且左子结点 就是要删除结点，就将this.left = null; 并且就返回(结束递归删除)
if(this.left != null && this.left.no == no) {
this.left = null;
return;
}
//3.如果当前结点的右子结点不为空，并且右子结点 就是要删除结点，就将this.right= null ;并且就返回(结束递归删除)
if(this.right != null && this.right.no == no) {
this.right = null;
return;
}
//4.我们就需要向左子树进行递归删除
if(this.left != null) {
this.left.delNode(no);
}
//5.则应当向右子树进行递归删除
if(this.right != null) {
this.right.delNode(no);
}
}
//编写前序遍历的方法
public void preOrder() {
System.out.println(this); //先输出父结点
//递归向左子树前序遍历
if(this.left != null) {
this.left.preOrder();
}
//递归向右子树前序遍历
if(this.right != null) {
this.right.preOrder();
}
}
//中序遍历
public void infixOrder() {
//递归向左子树中序遍历
if(this.left != null) {
this.left.infixOrder();
}
//输出父结点
System.out.println(this);
//递归向右子树中序遍历
if(this.right != null) {
this.right.infixOrder();
}
}
//后序遍历
public void postOrder() {
if(this.left != null) {
this.left.postOrder();
}
if(this.right != null) {
this.right.postOrder();
}
System.out.println(this);
}
//前序遍历查找
/**
*
* @param no 查找no
* @return 如果找到就返回该Node ,如果没有找到返回 null
*/
public HeroNode preOrderSearch(int no) {
System.out.println("进入前序遍历");
//比较当前结点是不是
if(this.no == no) {
return this;
}
//1.则判断当前结点的左子节点是否为空，如果不为空，则递归前序查找
//2.如果左递归前序查找，找到结点，则返回
HeroNode resNode = null;
if(this.left != null) {
resNode = this.left.preOrderSearch(no);
}
if(resNode != null) {//说明我们左子树找到
return resNode;
}
//1.左递归前序查找，找到结点，则返回，否继续判断，
//2.当前的结点的右子节点是否为空，如果不空，则继续向右递归前序查找
if(this.right != null) {
resNode = this.right.preOrderSearch(no);
}
return resNode;
}
//中序遍历查找
public HeroNode infixOrderSearch(int no) {
//判断当前结点的左子节点是否为空，如果不为空，则递归中序查找
HeroNode resNode = null;
if(this.left != null) {
resNode = this.left.infixOrderSearch(no);
}
if(resNode != null) {
return resNode;
}
System.out.println("进入中序查找");
//如果找到，则返回，如果没有找到，就和当前结点比较，如果是则返回当前结点
if(this.no == no) {
return this;
}
//否则继续进行右递归的中序查找
if(this.right != null) {
resNode = this.right.infixOrderSearch(no);
}
return resNode;
}
//后序遍历查找
public HeroNode postOrderSearch(int no) {
//判断当前结点的左子节点是否为空，如果不为空，则递归后序查找
HeroNode resNode = null;
if(this.left != null) {
resNode = this.left.postOrderSearch(no);
}
if(resNode != null) {//说明在左子树找到
return resNode;
}
//如果左子树没有找到，则向右子树递归进行后序遍历查找
if(this.right != null) {
resNode = this.right.postOrderSearch(no);
}
if(resNode != null) {
return resNode;
}
System.out.println("进入后序查找");
//如果左右子树都没有找到，就比较当前结点是不是
if(this.no == no) {
return this;
}
return resNode;
}
}
二叉树-结点删除
1、规定：
- 如果删除的是叶子结点，则直接删除该节点
- 如果删除的非叶子结点，则删除该节点树
思路：
- 首先处理：判断是否为空树，如果只有root一个节点，等价于二叉树置空
- 通过递归方式，进行遍历，判断是该节点的子节点是否为需要删除的节点，如果是，则this.left=null;返回递归，或者this.right=null；结束递归。
规定：
- 如果叶子节点，直接删除。
- 如果非叶子节点，仅仅删除该节点，然后找到左子树最右边叶子结点，替补该节点，或者找右子树，最左叶子结点，替代要删除的节点。
思路：
- 首先处理：判断是否为空树，如果只有root一个节点，等价于二叉树置空
- 通过遍历（可以递归，也可以不递归），查找到需要删除的节点
- 查找删除节点的右子树的最左叶子结点，或者左子树的最右叶子结点
顺序存储二叉树
概念：
- 基本说明：从数据结构看，数组存储方式和树的存储方式可以互换，即数组可以转换成树，树也可以转换为数组
要求：
- 以数组方式存储树
- 遍历数组的时候，仍然可以用一起的前序，中序，后序方式完成结点遍历
顺序存储二叉树特点：
- 顺序二叉树通常只考虑二叉树
- 第n个元素的左子节点为2*n+1
- 第n个元素的右子节点为2*n+2
- 第n个元素的父节点为（n-1）/2
- n：表示二叉树中的第几个元素（按0开始编号）
代码实现：
//编写一个ArrayBinary'Tree,实现顺序存储二叉树遍历
class ArrBinaryTree
{
private int[r: ;
//存储数据结点的数组
public ArBinaryTree(int[] arr)
{
this.arr = arr;
}
//重载preOrder
public void preOrder()
{
this.preOrder(0);
}
// 编写一个方法， 完成顺序存储二叉树的前序遍历
/**
* @param index数组的下标
*/
public void preOrder(int index)
{
//如果数组为空，或者ar.length= 0
if(arr = null II arr.length == 0)
{
System.out.printn("数组为空，不能按照二叉树的前
//输出当前这个元素
Sytem.out.printlnfarr[index);
//向左递归遍历
if(index * 2 + 1) < arr.length)
{
preOrder(2 * index + 1);
//向右递归遍历
if(index * 2 + 2) < ar.length)
{
preOrder(2 * index + 2);
}
}
}
}
备注：八大排序算法中的堆排序，就会使用到顺序储存二叉树
线索二叉树
哈弗曼树
- 给定n个权值，最为n个叶子节点，构造一个二叉树，如果该树的代权路径长度（wpl）达到最小，称这个二叉树为最优二叉树，也称哈弗曼树。
- 哈弗曼树代权路径最短的树，权值较大，离节点较近。
代码实现：
package dataConstruct;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.LinkedList;
import java.util.List;
/**
* 哈夫曼树和哈夫曼编码， 1、哈夫曼树的构造 2、哈夫曼编码压缩和解压
*
* @author zhanbei
*
*/
public class Huffman {
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] arr = {1,2,3,5,69,8,7,4};
print(initHaffuMan(arr));
=
private static void print(TreeNode root) {
if (root == null) {
System.out.println("haffuMan树为空！");
}
// 前序遍历
System.out.println("输出最大节点，父节点--"+root.value);
}
/**
* 哈弗曼树构造
*/
private static TreeNode initHaffuMan(int[] arr) {
if (arr.length <= 0) {
System.out.println("数组为空，不可建立haffuman树");
return null;
}
List<TreeNode> treeNodes = new ArrayList<TreeNode>(arr.length);
for (int i = 0; i < arr.length; i++) {
treeNodes.add(new TreeNode(arr[i]));
}
return createHaffuMan(treeNodes);
}
private static TreeNode createHaffuMan(List<TreeNode> treeNodes) {
System.out.println(treeNodes.size());
while (treeNodes.size() > 1) {
TreeNode treeNode = null;
Collections.sort(treeNodes);
TreeNode left = treeNodes.get(0);
TreeNode right = treeNodes.get(1);
treeNode = new TreeNode(treeNodes.get(0).value + treeNodes.get(1).value);
treeNode.left = left ;
treeNode.right = right ;
treeNodes.remove(left);
treeNodes.remove(right);
treeNodes.add(treeNode);
}
return treeNodes.get(0);
}
}
class TreeNode implements Comparable<TreeNode> {
int value;
TreeNode right;
TreeNode left;
public TreeNode(int value) {
this.value = value;
right = null;
left = null;
// TODO Auto-generated constructor stub
}
@Override
public int compareTo(TreeNode arg0) {
// TODO Auto-generated method stub
return arg0.value - value;
}
}
