目录1、冒泡排序Bubble Sort2、快速排序Quick Sort3、选择排序Selection Sort4、堆排序Heap Sort5、插入排序Insertion Sort6、希尔排序Shell Sort7、归并排序Merge Sort其他排序8、计数排序Counting Sort9、桶排序Bucket Sort10、基数排序Radix Sort时间复杂度、空间复杂度、稳定性分析我们通常所说的排序算法往往指的是内部排序算法即数据记录在内存中进行排序分类如下① 交换排序冒泡排序、快速排序② 选择排序简单选择排序、堆排序③ 插入排序简单插入排序、希尔排序④ 归并排序二路归并、多路归并⑤ 其他排序计数排序、桶排序、基数排序1、冒泡排序Bubble Sort冒泡排序是一种简单的排序算法。它重复地走访过要排序的数列一次比较两个元素如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。1.1 算法描述比较相邻的元素。如果第一个比第二个大就交换它们两个对每一对相邻元素作同样的工作从开始第一对到结尾的最后一对这样在最后的元素应该会是最大的数针对所有的元素重复以上的步骤除了最后一个重复步骤1~3直到排序完成。1.2 动图演示1.3 代码实现public class ZJF { public static void main(String[] args) { int[] a {49, 38, 65, 97, 76, 13, 27, 49, 78, 34, 12, 64, 1, 8}; System.out.println(排序之前); for (int i 0; i a.length; i) { System.out.print(a[i] ); } // 冒泡排序 for (int i 0; i a.length; i) { for (int j 0; j a.length - i - 1; j) { // 这里-i主要是每遍历一次都把最大的i个数沉到最底下去了没有必要再替换了 if (a[j] a[j 1]) { int temp a[j]; a[j] a[j 1]; a[j 1] temp; } } } System.out.println(排序之后); for (int i 0; i a.length; i) { System.out.print(a[i] ); } } }1.4 算分分析冒泡排序一趟下来一个大值就会落下去直到最后所有的值有序。只要序列不是有序的中间肯定会有交换所以如果没有交换意味着序列已经有序。冒泡排序可以优化如下void bubble_sort_enhanced(int *a, int size) { int i, j, t; unsigned char swapped; for(i 1; i size; i) { swapped 0; for(j 0; j size - i; j) { if(a[j] a[j1]){ t a[j]; a[j] a[j1]; a[j1] t; swapped 1; } } if(!swapped) break; } }2、快速排序Quick Sort快速排序的基本思想通过一趟排序将待排记录分隔成独立的两部分其中一部分记录的关键字均比另一部分的关键字小则可分别对这两部分记录继续进行排序以达到整个序列有序。2.1 算法描述快速排序使用分治法来把一个串list分为两个子串sub-lists。具体算法描述如下从数列中挑出一个元素称为 “基准”pivot重新排序数列所有元素比基准值小的摆放在基准前面所有元素比基准值大的摆在基准的后面相同的数可以到任一边。在这个分区退出之后该基准就处于数列的中间位置。这个称为分区partition操作递归地recursive把小于基准值元素的子数列和大于基准值元素的子数列排序。2.2 动图演示2.3 代码实现quicksort一个教科书式的简单实现采用左端点做pivot(《算法导论》上伪代码是以右端点做pivot)public void qsort1(int[] a, int p, int r) { // 0个或1个元素返回 if (p r) return; // 选择左端点为pivot int x a[p]; int j p; for (int i p 1; i r; i) { // 小于pivot的放到左边 if (a[i] x) { swap(a, j, i); } } // 交换左端点和pivot位置 swap(a, p, j); // 递归子序列 qsort1(a, p, j - 1); qsort1(a, j 1, r); }其中的swap用于交换数组元素public static void swap(int[] a, int i, int j) { int temp a[i]; a[i] a[j]; a[j] temp; }2.4 算法分析Java系统提供的Arrays.sort函数使用的就是快速排序。JDK1.7之后排序算法做了大幅度修改使用了双轴快排以减少随机选的单轴数据不“均衡”带来的性能偏差很明显每次选的轴大小正好处在中间位置最好。2.5 左右指针法2.6 双轴快排3、选择排序Selection Sort选择排序(Selection-sort)是一种简单直观的排序算法。它的工作原理首先在未排序序列中找到最小大元素存放到排序序列的起始位置然后再从剩余未排序元素中继续寻找最小大元素然后放到已排序序列的末尾。以此类推直到所有元素均排序完毕。3.1 算法描述n个记录的直接选择排序可经过n-1趟直接选择排序得到有序结果。具体算法描述如下初始状态无序区为R[1..n]有序区为空第i趟排序(i1,2,3…n-1)开始时当前有序区和无序区分别为R[1..i-1]和R(i..n。该趟排序从当前无序区中-选出关键字最小的记录 R[k]将它与无序区的第1个记录R交换使R[1..i]和R[i1..n)分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区n-1趟结束数组有序化了。3.2 动图演示3.3 代码实现public class ZJF { // 简单的选择排序 public static void main(String[] args) { int[] a {49, 38, 65, 97, 76, 13, 27, 49, 78, 34, 12, 64, 1, 8}; System.out.println(排序之前); for (int i 0; i a.length; i) { System.out.print(a[i] ); } // 简单的选择排序 for (int i 0; i a.length; i) { int min a[i]; // 最小数值 int minindex i; // 最小数的索引 for (int j i 1; j a.length; j) { if (a[j] min) { // 找出最小的数 min a[j]; minindex j; } } //交换 a[minindex] a[i]; a[i] min; } System.out.println(\n 排序之后); for (int i 0; i a.length; i) { System.out.print(a[i] ); } } }3.4 算法分析选择排序先假定第一个值为小或者最大者依次排查之后的数据找出真正的最大或者最小者然后交换直到最后。4、堆排序Heap Sort堆排序Heapsort是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构并同时满足堆积的性质即子结点的键值或索引总是小于或者大于它的父节点。4.1 算法描述将初始待排序关键字序列(R1,R2….Rn)构建成大顶堆此堆为初始的无序区将堆顶元素R[1]与最后一个元素R[n]交换此时得到新的无序区(R1,R2,……Rn-1)和新的有序区(Rn),且满足R[1,2…n-1]R[n]由于交换后新的堆顶R[1]可能违反堆的性质因此需要对当前无序区(R1,R2,……Rn-1)调整为新堆然后再次将R[1]与无序区最后一个元素交换得到新的无序区(R1,R2….Rn-2)和新的有序区(Rn-1,Rn)。不断重复此过程直到有序区的元素个数为n-1则整个排序过程完成。4.2 动图演示4.3 代码实现public class ZJF { // 堆排序 public static void main(String[] args) { int[] a {5, 4, 1, 2, 6, 3, 7, 9, 8, 0}; int arrayLength a.length; // 循环建堆 for (int i 0; i arrayLength - 1; i) { // 建堆 buildMaxHeap(a, arrayLength - 1 - i); // 交换堆顶和最后一个元素 swap(a, 0, arrayLength - 1 - i); System.out.println(Arrays.toString(a)); } } // 对data数组从0到lastIndex建大顶堆 public static void buildMaxHeap(int[] data, int lastIndex) { // 从lastIndex处节点最后一个节点的父节点开始 for (int i (lastIndex - 1) / 2; i 0; i--) { // k保存正在判断的节点 int k i; // 如果当前k节点的子节点存在 while (k * 2 1 lastIndex) { // k节点的左子节点的索引 int biggerIndex 2 * k 1; // 如果biggerIndex小于lastIndex即biggerIndex1代表的k节点的右子节点存在 if (biggerIndex lastIndex) { // 若果右子节点的值较大 if (data[biggerIndex] data[biggerIndex 1]) { // biggerIndex总是记录较大子节点的索引 biggerIndex; } } // 如果k节点的值小于其较大的子节点的值 if (data[k] data[biggerIndex]) { // 交换他们 swap(data, k, biggerIndex); // 将biggerIndex赋予k开始while循环的下一次循环重新保证k节点的值大于其左右子节点的值 k biggerIndex; } else { break; } } } } // 交换 private static void swap(int[] data, int i, int j) { int tmp data[i]; data[i] data[j]; data[j] tmp; } }4.4 算法分析算法的核心就是建堆建完“取下”一个堆顶继续建堆直到最后一个元素。因此算法的核心就是建堆其实buildMaxHeap()方法还有个简化版本如下// 对data数组从0到lastIndex建大顶堆 public static void buildMaxHeap(int[] data, int lastIndex) { // 从lastIndex处节点最后一个节点的父节点开始(在构造有序堆时我们开始只需要扫描一半的元素n/2-1 ~ 0即可为什么? 因为(n/2-1)~0的节点才有子节点) for (int i (lastIndex - 1) / 2; i 0; i--) { // k保存正在判断的节点 int k i; // k节点的左子节点的索引 int biggerIndex 2 * k 1; // 如果biggerIndex小于lastIndex即biggerIndex1代表的k节点的右子节点存在(实际上只有最后一个父节点才可能只有一个左字节点) if (biggerIndex lastIndex) { // 若果右子节点的值较大 if (data[biggerIndex] data[biggerIndex 1]) { // biggerIndex总是记录较大子节点的索引 biggerIndex; } } // 如果k节点的值小于其较大的子节点的值 if (data[k] data[biggerIndex]) { // 交换他们 swap(data, k, biggerIndex); } } }这个版本算法每次得到的堆顶一定会是最大值或者最小值但此时堆不是完全意义上的“堆”。建堆的过程是比较、交换父子节点的过程交换后不递归下一层子树会导致某个子树不符合堆的特点但是经测试这种方式效率反而更高也可能跟输入的数据有关需要后续分析时间复杂度给出答案。5、插入排序Insertion Sort插入排序Insertion-Sort的算法描述是一种简单直观的排序算法。它的工作原理是通过构建有序序列对于未排序数据在已排序序列中从后向前扫描找到相应位置并插入。5.1 算法描述一般来说插入排序都采用in-place在数组上实现。具体算法描述如下从第一个元素开始该元素可以认为已经被排序取出下一个元素在已经排序的元素序列中从后向前扫描如果该元素已排序大于新元素将该元素移到下一位置重复步骤3直到找到已排序的元素小于或者等于新元素的位置将新元素插入到该位置后重复步骤2~5。5.2 动图演示5.3 代码实现public class ZJF { // 直接插入排序 public static void main(String[] args) { int[] a {1, 4, 6, 2, 9, 5, 8, 6, 7}; System.out.print(排序前:); for (int i 0; i a.length; i) { System.out.print(a[i] ); } for (int i 1; i a.length; i) { int temp a[i]; int j; for (j i - 1; j 0; j--) { // 如果当前元素大于temp则将其往后移动一位 if (a[j] temp) { a[j 1] a[j]; } else { break; } } // 将最后往前移动的元素的原索引位置设置为temp的值如果没有一个往前移动的等于重新给自己赋了一遍自己的值 a[j 1] temp; } System.out.print(\n排序后:); for (int i 0; i a.length; i) { System.out.print(a[i] ); } } }5.4 算法分析与选择排序类似都是就地排序选择排序是每次选择合适的值放到有序队列的队尾选择的过程是在非有序数据队列中比较。插入排序是每次从非有序队列中拿出一个值找到合适的位置插入到有序队列中找位置的过程是跟有序列队列的值比较的过程“插队”会使后面的“人”依次挪动了一个位置跟现实生活中按照身高插队排序非常相似。5.5 二分插入排序6、希尔排序Shell Sort1959年Shell发明第一个突破O(n2)的排序算法是简单插入排序的改进版。它与插入排序的不同之处在于它会优先比较距离较远的元素。希尔排序又叫缩小增量排序。6.1 算法描述先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序具体算法描述选择一个增量序列t1t2ti,tj…tk其中titjtk1比如 4 2 1按增量序列个数k对序列进行k 趟排序比如增量为4时第一个序列index为0 4 8...第二个序列index为 1 5 9...第三个序列index为 2,6,10 ,一个增量K为一趟排序每一趟其实都有多个子序列排队。每趟排序根据对应的增量ti将待排序列分割成若干长度为m 的子序列分别对各子表进行直接插入排序。仅增量因子为1 时整个序列作为一个表来处理表长度即为整个序列的长度。6.2 动图演示6.3 代码实现public class ZJF { //希尔排序 public static void main(String[] args) { int[] list {9, 1, 2, 5, 7, 4, 8, 6, 3, 5}; int gap list.length; for (gap gap / 2; gap 0; gap gap / 2) { // 把距离为 gap 的元素编为一个组扫描所有组 for (int i 0; i gap; i) { // 对距离为 gap 的元素组进行直接插入排序 for (int j i gap; j list.length; j j gap) { int k; int temp list[j]; for (k j - gap; k 0; k k - gap) { if(temp list[k]) { list[k gap] list[k]; } else { break; } } list[k gap] temp; } } } System.out.print(\n排序后); for (int i 0; i list.length; i) { System.out.print(list[i] ); } } }6.4 算法分析希尔排序的核心在于间隔序列的设定。既可以提前设定好间隔序列也可以动态的定义间隔序列。动态定义间隔序列的算法是《算法第4版》的合著者Robert Sedgewick提出的。希尔排序通过将比较的全部元素分为几个区域来提升插入排序的性能。这样可以让一个元素可以一次性地朝最终位置前进一大步。然后算法再取越来越小的步长进行排序算法的最后一步就是普通的插入排序但是到了这步需排序的数据几乎是已排好的了此时插入排序较快。7、归并排序Merge Sort归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法Divide and Conquer的一个非常典型的应用。将已有序的子序列合并得到完全有序的序列即先使每个子序列有序再使子序列段间有序。若将两个有序表合并成一个有序表称为2-路归并。7.1 算法描述把长度为n的输入序列分成两个长度为n/2的子序列对这两个子序列分别采用归并排序将两个排序好的子序列合并成一个最终的排序序列。7.2 动图演示7.3 代码实现public class MergeSort { public static void main(String []args){ int []arr {9,8,7,6,5,4,3,2,1}; sort(arr); System.out.println(Arrays.toString(arr)); } public static void sort(int []arr){ int []temp new int[arr.length];//在排序前先建好一个长度等于原数组长度的临时数组避免递归中频繁开辟空间 sort(arr,0,arr.length-1,temp); } private static void sort(int[] arr,int left,int right,int []temp){ if(leftright){ int mid (leftright)/2; sort(arr,left,mid,temp);//左边归并排序使得左子序列有序 sort(arr,mid1,right,temp);//右边归并排序使得右子序列有序 merge(arr,left,mid,right,temp);//将两个有序子数组合并操作 } } private static void merge(int[] arr,int left,int mid,int right,int[] temp){ int i left;//左序列指针 int j mid1;//右序列指针 int t 0;//临时数组指针 while (imid jright){ if(arr[i]arr[j]){ temp[t] arr[i]; }else { temp[t] arr[j]; } } while(imid){//将左边剩余元素填充进temp中 temp[t] arr[i]; } while(jright){//将右序列剩余元素填充进temp中 temp[t] arr[j]; } t 0; //将temp中的元素全部拷贝到原数组中 while(left right){ arr[left] temp[t]; } } }7.4 算法分析归并排序是稳定排序它也是一种十分高效的排序能利用完全二叉树特性的排序一般性能都不会太差。java中Arrays.sort()采用了一种名为TimSort的排序算法就是归并排序的优化版本。(数据量小使用归并排序数据量大使用快排快排又根据数据量分成了简单快排、双轴快排)。7.5 多路归并其他排序8、计数排序Counting Sort计数排序不是基于比较的排序算法其核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。 作为一种线性时间复杂度的排序计数排序要求输入的数据必须是有确定范围的整数。8.1 算法描述找出待排序的数组中最大和最小的元素统计数组中每个值为i的元素出现的次数存入数组C的第i项对所有的计数累加从C中的第一个元素开始每一项和前一项相加反向填充目标数组将每个元素i放在新数组的第C(i)项每放一个元素就将C(i)减去1。8.2 动图演示8.3 代码实现public static int[] countSort1(int[] arr){ if (arr null || arr.length 0) { return null; } int max Integer.MIN_VALUE; int min Integer.MAX_VALUE; //找出数组中的最大最小值 for(int i 0; i arr.length; i){ max Math.max(max, arr[i]); min Math.min(min, arr[i]); } int help[] new int[max]; //找出每个数字出现的次数 for(int i 0; i arr.length; i){ int mapPos arr[i] - min; help[mapPos]; } int index 0; for(int i 0; i help.length; i){ while(help[i]-- 0){ arr[index] imin; } } return arr; }9、桶排序Bucket Sort桶排序是计数排序的升级版。它利用了函数的映射关系高效与否的关键就在于这个映射函数的确定。桶排序 (Bucket sort)的工作的原理假设输入数据服从均匀分布将数据分到有限数量的桶里每个桶再分别排序有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排。9.1 算法描述设置一个定量的数组当作空桶遍历输入数据并且把数据一个一个放到对应的桶里去对每个不是空的桶进行排序从不是空的桶里把排好序的数据拼接起来。9.2 图片演示9.3 代码实现public static void bucketSort(int[] arr){ int max Integer.MIN_VALUE; int min Integer.MAX_VALUE; for(int i 0; i arr.length; i){ max Math.max(max, arr[i]); min Math.min(min, arr[i]); } //桶数 int bucketNum (max - min) / arr.length 1; ArrayListArrayListInteger bucketArr new ArrayList(bucketNum); for(int i 0; i bucketNum; i){ bucketArr.add(new ArrayListInteger()); } //将每个元素放入桶 for(int i 0; i arr.length; i){ int num (arr[i] - min) / (arr.length); bucketArr.get(num).add(arr[i]); } //对每个桶进行排序 for(int i 0; i bucketArr.size(); i){ Collections.sort(bucketArr.get(i)); } System.out.println(bucketArr.toString()); }10、基数排序Radix Sort基数排序已经不再是一种常规的排序方式它更多地像一种排序方法的应用基数排序必须依赖于另外的排序方法。基数排序的总体思路就是将待排序数据拆分成多个关键字进行排序也就是说基数排序的实质是多关键字排序。如果按照习惯思维会先比较百位百位大的数据大百位相同的再比较十位十位大的数据大最后再比较个位。人得习惯思维是最高位优先方式。但一旦这样当开始比较十位时程序还需要判断它们的百位是否相同--这就认为地增加了难度计算机通常会选择最低位优先法。基数排序方法对任一子关键字排序时必须借助于另一种排序方法而且这种排序方法必须是稳定的。对于多关键字拆分出来的子关键字它们一定位于0-9这个可枚举的范围内这个范围不大因此用桶式排序效率非常好。对于多关键字排序来说程序将待排数据拆分成多个子关键字后对子关键字排序既可以使用桶式排序也可以使用任何一种稳定的排序方法。10.1 算法描述取得数组中的最大数并取得位数arr为原始数组从最低位开始取每个位组成radix数组对radix进行计数排序利用计数排序适用于小范围数的特点10.2 动图演示10.3 算法分析基数排序只是“其他”排序的进一步使用犹如桶排序。有人认为基数排序是桶排序的演化个人认为是不对的他只是多关键字排序跟“桶排序”没有关系。这里给出一个思路可以构造一个排序类包含两个属性第一个存储排序元素第二个存储当前排序的位数上的数字将这些包装类放到list里直接利用jdk的sortsort使用自定义的比较器比较元素的第二个属性。当然外层需要一个循环缓存次数为排序元素的长度以最长的为准不够的补0每趟排序完需要给每个元素的第二个参数重新赋值下一位上的数字。时间复杂度、空间复杂度、稳定性分析参考http://www.cnblogs.com/liuling/p/2013-7-24-01.htmlhttps://www.cnblogs.com/onepixel/articles/7674659.htmlhttp://www.cnblogs.com/eniac12/p/5329396.htmlhttp://www.cnblogs.com/jingmoxukong/p/4303279.htmlhttp://www.360doc.com/content/14/0507/19/18042_375598267.shtmlhttp://www.cnblogs.com/MOBIN/p/5374217.htmlhttp://www.blogjava.net/killme2008/archive/2010/09/08/quicksort_optimized.htmlhttps://www.cnblogs.com/jiqingwu/p/bubble_sort_analysis.htmlhttps://www.cnblogs.com/protected/p/6603536.htmlhttps://www.cnblogs.com/skywang12345/p/3603669.html