算法界的Hello,world之—八大排序,三大查找算法[Java实现]！Think-Yang-

简介

在CS界曾流行这样一种说法：算法不是万能的，但是没有算法是万万不能的。作为一个具有基本素养的计算机科学从业者，可以说这些是必须知道的。从算法的Easy级别入手，当然要从大家口中常说的，八大排序三大查找开始啦~~~

排序算法

排序算法可以大致分成分成5大块：插入，选择，交换，归并，基数等等排序方式，下面就一一介绍这几种排序方式。

一，直接插入排序（Straight Insertion Sort）：

直接插入排序：通常人们整理桥牌的方法是一张一张的来，将每一张牌插入到其他已经有序的牌中的适当位置。在计算机的实现中，为了要给插入的元素腾出空间，我们需要将其余所有元素在插入之前都向右移动一位。插入排序是稳定的。

• 算法描述

1. 从第一个元素开始，该元素可以认为已经被排序
2. 取出下一个元素，在已经排序的元素序列中从后向前扫描
3. 如果该元素（已排序）大于新元素，将该元素移到下一位置
4. 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
5. 将新元素插入到该位置后
6. 重复步骤2~5

• 动态效果图
  

• 代码实现

/**  * 通过交换进行插入排序，借鉴冒泡排序  *  * @param a  */ public static void siSort(int[] a) { for (int i = 0; i < a.length - 1; i++) { for (int j = i + 1; j > 0; j--) { if (a[j] < a[j - 1]) { int temp = a[j];                 a[j] = a[j - 1];                 a[j - 1] = temp; } } } } /**  * 通过将较大的元素都向右移动而不总是交换两个元素  *  * @param a  */ public static void siSort2(int[] a) { for (int i = 1; i < a.length; i++) { int num = a[i]; int j; for (j = i; j > 0 && num < a[j - 1]; j--) {             a[j] = a[j - 1]; }         a[j] = num; } } 

二，希尔排序（Shells Sort）：

希尔排序，一个叫希尔的人发明的排序算法：希尔排序是按照不同步长对元素进行插入排序，一次插入排序是稳定的，不会改变相同元素的相对顺序，但在不同的插入排序过程中，相同的元素可能在各自的插入排序中移动，稳定性就会被破坏，所以希尔排序不稳定。

• 算法描述

1. 选择一个增量序列 t1，t2，……，tk，其中 ti > tj, tk = 1；
2. 按增量序列个数 k，对序列进行 k 趟排序；
3. 每趟排序，根据对应的增量 ti，将待排序列分割成若干长度为 m 的子序列，分别对各子表进行直接插入排序。仅增量因子为 1
   时，整个序列作为一个表来处理，表长度即为整个序列的长度。

• 效果图
  
• 代码实现

public static void shellSort(int[] a) { int length = a.length; int h = 1; while (h < length / 3) h = 3 * h + 1; for (; h >= 1; h /= 3) { for (int i = 0; i < a.length - h; i += h) { for (int j = i + h; j > 0; j -= h) { if (a[j] < a[j - h]) { int temp = a[j];                     a[j] = a[j - h];                     a[j - h] = temp; } } } } } 

三，简单选择排序（Straight Selection Sort）：

简单选择排序：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

• 算法描述

1. 从未排序序列中，找到关键字最小的元素
2. 如果最小元素不是未排序序列的第一个元素，将其和未排序序列第一个元素互换
3. 重复1、2步，直到排序结束。

• 效果图
  
• 代码实现

public static void ssSort(int[] a) { for (int i = 0; i < a.length; i++) { int min = i; //选出之后待排序中值最小的位置 for (int j = i + 1; j < a.length; j++) { if (a[j] < a[min]) {                 min = j; } } //最小值不等于当前值时进行交换 if (min != i) { int temp = a[i];             a[i] = a[min];             a[min] = temp; } } } 

四，堆排序（Heap Sort）：

堆排序：
堆的定义如下：n个元素的序列{k1,k2,…,kn}
当且仅当满足下关系时，称之为堆。

把此序列对应的二维数组看成一个完全二叉树。那么堆的含义就是：完全二叉树中任何一个非叶子节点的值均不大于（或不小于）其左，右孩子节点的值。 由上述性质可知大顶堆的堆顶的关键字肯定是所有关键字中最大的，小顶堆的堆顶的关键字是所有关键字中最小的。因此我们可使用大顶堆进行升序排序, 使用小顶堆进行降序排序。

• 算法描述

1. 先将初始序列K[1…n]建成一个大顶堆, 那么此时第一个元素K1最大, 此堆为初始的无序区.

2. 再将关键字最大的记录K1 (即堆顶, 第一个元素)和无序区的最后一个记录 Kn 交换,
   由此得到新的无序区K[1…n−1]和有序区K[n], 且满足K[1…n−1].keys⩽K[n].key

3. 交换K1 和 Kn 后, 堆顶可能违反堆性质, 因此需将K[1…n−1]调整为堆. 然后重复步骤2, 直到无序区只有一个元素时停止。

• 效果图
  
• 代码实现

/**  * @param a  */ public static void heapSort(int[] a) { for (int i = a.length - 1; i > 0; i--) { max_heapify(a, i); //堆顶元素(第一个元素)与Kn交换 int temp = a[0];         a[0] = a[i];         a[i] = temp; } } /***  *  *  将数组堆化  *  i = 第一个非叶子节点。  *  从第一个非叶子节点开始即可。无需从最后一个叶子节点开始。  *  叶子节点可以看作已符合堆要求的节点，根节点就是它自己且自己以下值为最大。  *  * @param a  * @param n  */ public static void max_heapify(int[] a, int n) { int child; for (int i = (n - 1) / 2; i >= 0; i--) { //左子节点位置         child = 2 * i + 1; //右子节点存在且大于左子节点，child变成右子节点 if (child != n && a[child] < a[child + 1]) {             child++; } //交换父节点与左右子节点中的最大值 if (a[i] < a[child]) { int temp = a[i];             a[i] = a[child];             a[child] = temp; } } } 

五，冒泡排序（Bubble Sort）：

冒泡排序：由前面的内容可知，冒泡排序是相邻的两个元素比较，交换也发生在这两个元素之间，如果两个元素相等，不用交换。所以冒泡排序稳定。

• 算法描述

1. 比较相邻的元素。如果第一个比第二个大，就交换他们两个。

2. 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。

3. 针对所有的元素重复以上的步骤，除了最后一个。

4. 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

• 效果图
  

• 代码实现

public static void sort(int[] a) { //外层循环控制比较的次数 for (int i = 0; i < a.length - 1; i++) { //内层循环控制到达位置 for (int j = 0; j < a.length - i - 1; j++) { //前面的元素比后面大就交换 if (a[j] > a[j + 1]) { int temp = a[j];                 a[j] = a[j + 1];                 a[j + 1] = temp; } } } } 

六，快速排序（Quick Sort）：

快速排序：快速排序的基本思想：挖坑填数+分治法。
快速排序使用分治法（Divide and conquer）策略来把一个串行（list）分为两个子串行（sub-lists）。
快速排序又是一种分而治之思想在排序算法上的典型应用。本质上来看，快速排序应该算是在冒泡排序基础上的递归分治法。
快速排序的名字起的是简单粗暴，因为一听到这个名字你就知道它存在的意义，就是快，而且效率高！它是处理大数据最快的排序算法之一了。虽然 Worst Case 的时间复杂度达到了 O(n²)，但是人家就是优秀，在大多数情况下都比平均时间复杂度为 O(n logn) 的排序算法表现要更好。

• 算法描述

快速排序使用分治策略来把一个序列（list）分为两个子序列（sub-lists）。步骤为：

1. 从数列中挑出一个元素，称为”基准”（pivot）。

2. 重新排序数列，所有比基准值小的元素摆放在基准前面，所有比基准值大的元素摆在基准后面（相同的数可以到任一边）。在这个分区结束之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。

3. 递归地（recursively）把小于基准值元素的子数列和大于基准值元素的子数列排序。

递归到最底部时，数列的大小是零或一，也就是已经排序好了。这个算法一定会结束，因为在每次的迭代（iteration）中，它至少会把一个元素摆到它最后的位置去。

• 效果图
  

• 代码实现

public static void quickSort(int[] a, int low, int high) { //已经排完 if (low >= high) { return; } int left = low; int right = high; //保存基准值 int pivot = a[left]; while (left < right) { //从后向前找到比基准小的元素 while (left < right && a[right] >= pivot)             right--;         a[left] = a[right]; //从前往后找到比基准大的元素 while (left < right && a[left] <= pivot)             left++;         a[right] = a[left]; } // 放置基准值，准备分治递归快排     a[left] = pivot; sort(a, low, left - 1); sort(a, left + 1, high); } 

七，归并排序（Merge Sort）：

归并排序：并排序算法是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列。归并排序也是稳定的。

• 算法描述

归并排序可通过两种方式实现:

• 自上而下的递归
• 自下而上的迭代

一： 递归法（假设序列共有n个元素）：

将序列每相邻两个数字进行归并操作，形成 floor(n/2)个序列，排序后每个序列包含两个元素；
将上述序列再次归并，形成 floor(n/4)个序列，每个序列包含四个元素；
重复步骤2，直到所有元素排序完毕。

二： 迭代法：

1. 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列

2. 设定两个指针，最初位置分别为两个已经排序序列的起始位置

3. 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置

4. 重复步骤3直到某一指针到达序列尾

5. 将另一序列剩下的所有元素直接复制到合并序列尾

• 代码实现（递归方法）

public class Merge { //归并所需的辅助数组 private static int[] aux; public static void sort(int[] a) { //一次性分配空间         aux = new int[a.length]; sort(a, 0, a.length - 1); } public static void sort(int[] a, int low, int high) { if (low >= high) { return; } int mid = (low + high) / 2; //将左半边排序 sort(a, low, mid); //将右半边排序 sort(a, mid + 1, high); merge(a, low, mid, high); } /**      * 该方法先将所有元素复制到aux[]中，然后在归并会a[]中。方法咋归并时(第二个for循环)      * 进行了4个条件判断：      * - 左半边用尽(取右半边的元素)      * - 右半边用尽(取左半边的元素)      * - 右半边的当前元素小于左半边的当前元素(取右半边的元素)      * - 右半边的当前元素大于等于左半边的当前元素(取左半边的元素)      * @param a      * @param low      * @param mid      * @param high      */ public static void merge(int[] a, int low, int mid, int high) { //将a[low..mid]和a[mid+1..high]归并 int i = low, j = mid + 1; for (int k = low; k <= high; k++) {             aux[k] = a[k]; } for (int k = low; k <= high; k++) { if (i > mid) {                 a[k] = aux[j++]; } else if (j > high) {                 a[k] = aux[i++]; } else if (aux[j] < aux[i]) {                 a[k] = aux[j++]; } else {                 a[k] = aux[i++]; } } } } 

八，基数排序（Radix Sort）/ 桶排序（Bucket Sort）：

基数排序：
基数排序的发明可以追溯到1887年赫尔曼·何乐礼在打孔卡片制表机（Tabulation Machine）, 排序器每次只能看到一个列。它是基于元素值的每个位上的字符来排序的。 对于数字而言就是分别基于个位，十位， 百位或千位等等数字来排序。
具体是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。有时候有些属性是有优先级顺序的，先按低优先级排序，再按高优先级排序，最后的次序就是高优先级高的在前，高优先级相同的低优先级高的在前。基数排序基于分别排序，分别收集，所以是稳定的。

• 算法描述

通过序列中各个元素的值，对排序的N个元素进行若干趟的“分配”与“收集”来实现排序。

• 分配：我们将L[i]中的元素取出，首先确定其个位上的数字，根据该数字分配到与之序号相同的桶中

• 收集：当序列中所有的元素都分配到对应的桶中，再按照顺序依次将桶中的元素收集形成新的一个待排序列L[]。对新形成的序列L[]重复执行分配和收集元素中的十位、百位…直到分配完该序列中的最高位，则排序结束

• 效果图
  

• 代码实现

public static void radixSort(int[] arr) { if (arr.length <= 1) return; //取得数组中的最大数，并取得位数 int max = 0; for (int i = 0; i < arr.length; i++) { if (max < arr[i]) {             max = arr[i]; } } int maxDigit = 1; while (max / 10 > 0) {         maxDigit++;         max = max / 10; } //申请一个桶空间 int[][] buckets = new int[10][arr.length]; int base = 10; //从低位到高位，对每一位遍历，将所有元素分配到桶中 for (int i = 0; i < maxDigit; i++) { int[] bktLen = new int[10]; //存储各个桶中存储元素的数量 //分配：将所有元素分配到桶中 for (int j = 0; j < arr.length; j++) { int whichBucket = (arr[j] % base) / (base / 10);             buckets[whichBucket][bktLen[whichBucket]] = arr[j];             bktLen[whichBucket]++; } //收集：将不同桶里数据挨个捞出来,为下一轮高位排序做准备,由于靠近桶底的元素排名靠前,因此从桶底先捞 int k = 0; for (int b = 0; b < buckets.length; b++) { for (int p = 0; p < bktLen[b]; p++) {                 arr[k++] = buckets[b][p]; } }         System.out.println("Sorting: " + Arrays.toString(arr));         base *= 10; } } 

查找算法

本文所说的三大查找算法称为三大类的查找算法，分别是：顺序、二分、分块。
其实还有个哈希查找，但是不在本文讨论范围之内

一，顺序查找 / 线性查找（Sequential Search）：

从表的一端开始，顺序扫描表，依次将扫描到的结点关键字和给定值（假定为a）相比较，若当前结点关键字与a相等，则查找成功；若扫描结束后，仍未找到关键字等于a的结点，则查找失败。

• 算法描述

说白了就是，从头到尾，一个一个地比，找着相同的就成功，找不到就失败。很明显的缺点就是查找效率低。
适用于线性表的顺序存储结构和链式存储结构。

• 代码实现

public static int seqSearch(int[] a, int key) { for (int i = 0, length = a.length; i < length; i++) { if (a[i] == key) return i; } return -1; } 

二，折半查找 / 二分查找（Binary Search）：

二分法查找适用于大的数据，但前提条件是数据必须是有序的，他的原理是先和中间的比较，如果等于就直接返回，如果小于就在前半部分继续使用二分法进行查找，如果大于则在后半部分继续使用二分法进行查找

• 代码实现

public static int binarySearch(int[] array, int value) { int low = 0; int high = array.length - 1; while (low <= high) { int middle = (low + high) >> 1; if (value == array[middle]) { return middle; } if (value > array[middle]) {             low = middle + 1; } if (value < array[middle]) {             high = middle - 1; } } return -1; } 

三，分块查找：

分块查找又称索引顺序查找，它是顺序查找的一种改进方法。
算法思想：将n个数据元素”按块有序”划分为m块（m ≤ n）。每一块中的结点不必有序，但块与块之间必须”按块有序”；即第1块中任一元素的关键字都必须小于第2块中任一元素的关键字；而第2块中任一元素又都必须小于第3块中的任一元素，……

• 算法描述

1. 先选取各块中的最大关键字构成一个索引表；

2. 查找分两个部分：先对索引表进行二分查找或顺序查找，以确定待查记录在哪一块中；

3. 然后，在已确定的块中用顺序法进行查找。

• 代码实现
  索引表的长度最佳为数据总长度开根号；

public class BlockSearch { private int[] index;//建立索引 private ArrayList[] list; /**   * @Descript:初始化索引   *   * @author LJonah 2018年3月12日   * @param index   */ public BlockSearch(int[] index){ if(null != index && index.length!=0){ this.index = index; this.list = new ArrayList[index.length]; for (int i = 0;i < list.length;i++) {     list[i] = new ArrayList();//初始化容器 } }else{ throw new Error("index cannot be null or empty"); } } /**   * @Descript:插入索引   *   * @author LJonah 2018年3月12日   * @param value   */ public void insert(int value){ int i = binarySearch(value);      list[i].add(value); } /**   * @Descript:二分法查找   *   * @author LJonah 2018年3月12日   * @param value   * @return   */ private int binarySearch(int value){ int start = 0,end =index.length;int mid = -1; while(start<=end){    mid=(start+end)/2; if(index[mid]>value){     end = mid -1; }else{ //如果相等，也插入后面     start = mid+1; } } return start; } /**      * @Descript:查找元素      *      * @author LJonah 2018年3月12日      * @param data      * @return      */ public boolean search(int data) { int i=binarySearch(data); for(int j=0;j<list[i].size();j++) { if(data==(int)list[i].get(j)) {                    System.out.println(String.format("查找元素为第: %d块  第%d个 元素",  i+1,j+1)); return true; } } return false; } /**   * @Descript:打印每块的元素   *   * @author LJonah 2018年3月12日   */ public void printAll(){ for (int i = 0; i < list.length; i++) {    ArrayList l = list[i];    System.out.println("ArrayList["+i+"]:"); for (int j = 0; j < l.size(); j++) {     System.out.println(l.get(j)+"    "); } } } /**   * @Descript:测试   *   * @author LJonah 2018年3月12日   * @param args   */ public static void main(String[] args) { int []index={10,20,30};            BlockSearch blocksearch=new BlockSearch(index);            blocksearch.insert(1);            blocksearch.insert(11);            blocksearch.insert(21);                        blocksearch.insert(2);            blocksearch.insert(12);            blocksearch.insert(22);                        blocksearch.insert(5);            blocksearch.insert(15);            blocksearch.insert(25);                        blocksearch.printAll();                          System.out.println("查找值15   结果"+blocksearch.search(15));            System.out.println("查找值29   结果"+blocksearch.search(29)); } } 

参考资料 & 致谢

【1】Java实现八大排序算法
【2】带你彻底搞定希尔排序是个什么情况
【3】分块查询算法(JAVA)