这个星期重新整顿了一些基本查找排序算法的实现，我承认自己不是一个很灵光的码农，还搞了几个小时才把这些最基本的代码给码出来。。。
查找：
1、基本查找：针对无序的数组查找一般只有从头部(下标0)依次查找，如果查找成功返回数组下标，查找失败返回-1
private static int commonSearch(int[] a, int b) { if (a == null) return -1; int len = a.length; for (int i = 0; i < len; i++) { if (a[i] == b) return i; } return -1; }
2、二分查找：针对有序表的查找，依次从数组下标的middle值找起，该值如果大于要查找值，则从该下标前部分继续查找，如该值小于要查找值，从该下标后半部分查找；查找成功
返回。查找失败返回-1.该算法时间复杂度可以只是O(logN)，速度较快。
private static int binarySearch(int[] a, int b) { if (a == null) return -1; int low = 0; int high = a.length - 1; while (low <= high) { int middle = (low + high) / 2; if (b == a[middle]) return middle; if (b > a[middle]) low = middle + 1; else high = middle - 1; } return -1; }
查找算法还有分块查找，二叉树查找，b树查找，hash查找木有实现，暑假的时候再来实现
排序：
1、插入排序：插入排序是依次将第n个元素插入到前n-1个已经排好序的元素中。即对于前n-1个已经排好序的元素，当第n个元素需要排序时，我们拿这个元素依次同前面的元素比较，如果该元素小于前面的元素时，就需交换二者的位置。时间复杂度O（n2），稳定排序。
本处实现的是带哨兵的插入排序，要求数组第一个元素不是有意义的元素，那么比较一个值a的时候可以将自己先放入第一个元素，则当a依次向前比较时，不用关心数组下标是否越界，因为比较到第一个元素时，a<a永远不成立。这样可以节省循环中大量的比较次数。
1 private static int[] insertSort(int[] a) { 2 if (null == a) 3 return null; 4 int len = a.length; 5 int[] b = new int[len + 1]; 6 System.arraycopy(a, 0, b, 1, len); 7 for (int i = 2; i <= len; i++) { 8 b[0] = b[i]; 9 10 for (int j = i - 1; b[j] > b[0]; j--) { 11 b[j + 1] = b[j]; 12 b[j] = b[0]; 13 } 14 } 15 16 System.arraycopy(b, 1, a, 0, len); 17 return a; 18 }
2、直接选择排序：依次在剩下的n-i个元素中选择一个最小的元素添加到前面已经排好序的i个元素之后。稳定排序，时间复杂度O(n2)。
是我个人觉得最烂的排序方式。。。无论怎样，这个排序也要神经兮兮的比较O(n2)次
private static int[] chooseSort(int[] a) { if (null == a) return null; int len = a.length; for (int i = 0; i < len - 1; i++) { int min = i; for (int j = i + 1; j < len; j++) if (a[j] < a[min]) { min = j; } int tmp = a[min]; a[min] = a[i]; a[i] = tmp; } return a; }
3、希尔排序：每次选定一个步长s对相隔s的元素进行排序，然后依次减少这个步长直到为1，属于插入排序，平均时间复杂度为O（n1.3），不知道怎么得来的，不稳定
1 private static int[] shellSort(int[] a) { 2 if (null == a) 3 return null; 4 int len = a.length; 5 for (int d = len / 2; d >= 1; d /= 2) { 6 for (int i = d; i < len; i++) { 7 int j, tmp = a[i]; 8 for (j = i - d; j >= 0 && tmp < a[j]; j -= d) 9 a[j + d] = a[j]; 10 a[j + d] = tmp; 11 } 12 } 13 return a; 14 }
4、冒泡排序：依次两两比较元素，将大的元素往后移，这样每一个的比较可以将前n个元素最大的元素移到尾部，然后依次次再对前n-1个元素进行比较。直到没有元素交换时停止。稳定排序，O(n2)的时间复杂度
1 private static int[] bubbleSort(int[] a) { 2 if (null == a) 3 return null; 4 int len = a.length; 5 int flag = len; 6 while (flag != 0) { 7 int n = flag; 8 flag = 0; 9 for (int i = 0; i < n - 1; i++) { 10 if (a[i] > a[i + 1]) { 11 swap(a, i, i + 1); 12 flag = i + 1; 13 } 14 } 15 System.out.print(Arrays.toString(a)); 16 if (flag == 0) 17 break; 18 } 19 return a; 20 }
5、快速排序：平均性能下最好的排序算法，不稳定，O（nlogn）的平均时间复杂度。
属于交换排序的一种，思想是依次选择一个pivot值，然后交换数组中元素，比该值小的元素交换至pivot前，比该值大的交换至pivot后。然后依次递归快排前后两个数组。
1 private static int[] quickSort(int[] a) { 2 if (null == a) 3 return null; 4 return quickSort(a, 0, a.length - 1); 5 } 6 7 private static int[] quickSort(int[] a, int low, int high) { 8 if (high > low) { 9 int pivot = partition(a, low, high); 10 System.out.println(Arrays.toString(a)); 11 quickSort(a, low, pivot - 1); 12 quickSort(a, pivot + 1, high); 13 } 14 return a; 15 } 16 17 private static int partition(int[] a, int low, int high) { 18 int i = low, j = high; 19 if (i < j) { 20 while (i < j && a[i] <= a[j]) 21 j--; 22 if (i < j) { 23 swap(a, i, j); 24 i++; 25 } 26 27 while (i < j && a[i] <= a[j]) 28 i++; 29 if (i < j) { 30 swap(a, i, j); 31 j--; 32 } 33 } 34 System.out.print(i); 35 return i; 36 }
6、归并排序：花了最多时间才写的排序，对自己智商开始捉急了。。。
归并排序过程就是将整个数组n个小划分，然后小划分内部排序之后，然后对这个小划分两两归并，同时进行，O（n）的空间复杂度，O（nlogn）的时间复杂度，稳定排序
有两种实现，一种递归实现，一种非递归实现。递归实现可以看坐自顶向下的归并过程，非递归实现可以看坐自下至顶的归并过程。
比如对于[1,2,3,4,5,6]来说，递归实现划分过程是划分成[1,2,3]和[4,5,6],然后[1,2,3]划分成[1,2]和[3]；而非递归过程是划分为[1,2][3,4][5,6],然后[1,2][3,4]归并成[1,2,3,4]最后和[5,6]归并成原始数组
递归实现：
private static int[] mergeSort(int[] a) { if (null == a) return a; int len = a.length; if (len == 0) return a; System.out.println(Arrays.toString(a)); return mergePassDC(a, 0, len - 1); // return mergePass(a, len - 1); } private static int[] mergePassDC(int[] a, int low, int high) { if (low < high) { int m = (low + high) / 2; mergePassDC(a, low, m); mergePassDC(a, m + 1, high); merge(a, low, m, high); System.out.println(Arrays.toString(a)); } return a; } private static int[] mergePass(int[] a, int n) { int d = 1; while (d <= n) { int i = 0; for (i = 0; i < n - 2 * d + 1; i += 2 * d) { merge(a, i, i + d - 1, i + 2 * d - 1); } if (i < n - d + 1) merge(a, i, i + d - 1, n); d *= 2; } return a; } private static void merge(int[] a, int low, int middle, int high) { int i = low, j = middle + 1, k = 0, len = high - low + 1; int[] a1 = new int[len]; while (i <= middle && j <= high) { if (a[i] <= a[j]) a1[k++] = a[i++]; else a1[k++] = a[j++]; } while (i <= middle) a1[k++] = a[i++]; while (j <= high) a1[k++] = a[j++]; System.arraycopy(a1, 0, a, low, len); }
7、堆排序：对于非递减排序，建立一个大顶堆（使得a[i]>=a[2*i],a[i]>=a[2*i+1]），那么依次选择第一个元素和最后一个元素交换时，再对前n-1个元素排序就可以得到一个非递减的数组。原理是一种选择排序，时间复杂度O（nlogn），不稳定
1 private static int[] heapSort(int[] a) { 2 if (null != a) { 3 int i, n = a.length - 1; 4 for (i = (n - 1) / 2; i >= 0; i--) 5 shift(a, i, n); 6 7 System.out.println("建立堆为 ："); 8 System.out.println(Arrays.toString(a)); 9 System.out.println(); 10 11 for (i = n; i >= 0; i--) { 12 swap(a, 0, i); 13 shift(a, 0, i - 1); 14 } 15 } 16 17 return a; 18 } 19 20 private static void shift(int[] a, int low, int high) { 21 int i = low, j = 2 * i + 1, tmp = a[i]; 22 while (j <= high) { 23 if (j < high && a[j] < a[j + 1]) 24 j++; 25 if (tmp < a[j]) { 26 a[i] = a[j]; 27 i = j; 28 j = 2 * i + 1; 29 } else 30 break; 31 } 32 a[i] = tmp; 33 }
基数排序没有实现，等暑假实现。
衷心希望今天实现的不要很快就忘掉。。。