面试中重要的排序算法

/** * 二分查找，找不到则返回一。 * @param a * @param key * @return */ public static int binarySearch(int[] a,int key){ int low =0,high=a.length-1; while (low<=high) { int mid = (low+high)/2; if (a[mid] == key) return mid; else if (a[mid] < key) low =mid+1; else high = mid-1; } return -1; } public static void sort(int[] a, int left, int right) { if (left >= right) return; int center = (left + right) >> 1; sort(a, left, center); sort(a, center + 1, right); merge(a, left, center, right); } public static void merge(int[] data, int i, int m, int n) { int[] tmpArr = new int[n]; int j,k; for (j = m+1, k=i; i<=m&&j<=n ; k++) { if (data[i] > data[j]) tmpArr[k] = data[j++]; else tmpArr[k] = data[i++]; } while (i<=m) tmpArr[k++]=data[i]; while (j<=n) tmpArr[k++] = data[j]; } public static void Msort(int[] sr,int s,int t){ if (s==t) return; if(s<=t){ int m= (s+t)/2; Msort(sr,s,m); Msort(sr,m+1,t); merge(sr,s,m,t); } } /** * 建堆（从(n-1)/2开始调整堆的结构） * @param a * @param n */ public static void heapSort(int[] a,int n){ for (int i = n/2-1; i >=0 ; i--) { adjustHeapDown(a,i,n); } } /** * 调整堆（从第i个结点开始向下调整） * @param a * @param n */ public static void adjustHeapDown(int[] a,int i,int n){ int tmp = a[i]; int j =2*i+1; while (j<n) { if ((j + 1) < n && a[j + 1] < a[j]) j = j + 1; //如果最小的子节点比根节点的值小，交换父节点和子节点的值,在往下调整子节点 if (a[j] < tmp) { a[i] = a[j]; i = j; j = 2 * i + 1; } else break;//若子节点的值比父节点的值，本来就是小根堆，同时说明树的子结构也满足要求，因此不需要继续往下调整。 } a[i] = tmp; } /** * 调整堆（从第i个结点开始向下调整） * @param a * @param n */ public static void deleteFromHeap(int[] a,int i,int n){ a[0] = a[n-1];//把最后一个元素复制到堆顶,开始往下调整 for (int j = 0; j <n-1 ; j++) { adjustHeapDown(a,0,n-1); } } /** * 快速排序 * @param a * @param low 数组的下边界 * @param high 数组的上边界 */ public static void quickSort(int[] a,int low,int high){ if (low<high) { int index = getQuickIndex(a,low,high); quickSort(a,low,index-1); quickSort(a,index+1,high); } } /** * 得到每次快排的索引 * @param a * @param low * @param high * @return */ public static int getQuickIndex(int[] a,int low,int high){ int tmp = a[low]; int i = low,j=high; while (i<j) { while (a[j] >tmp && i < j) j--; if (i < j) { a[i] = a[j]; i++; } while (a[i] <= tmp && i < j) i++; if (i < j) { a[j] = a[i]; j--; } } a[i]=tmp; return i; } /** * 插入排序 * @param a * @param n */ public static void zhiJieSort(int[] a,int n){ int j; for (int i = 1; i <n ; i++) { for (j = 0; j < i; j++) { //在有序的元素中找到第一个比当前大的 if (a[j] > a[i]) { break; } } //j到i-1的元素往后移动 if (j != i) { int tmp = a[i]; for (int k = i - 1; k >= j; k--) { a[k + 1] = a[k]; } a[j] = tmp; } } } /** * 选择排序 * @param a * @param n */ public static void choiceSort(int[] a,int n){ for (int i = 0; i <n ; i++) { int mini = i; for (int j = i+1; j <n ; j++) { if (a[j]<a[mini]) mini=j; } if (mini!=i){ int tmp = a[i]; a[i]=a[mini]; a[mini]=tmp; } } } /** * 冒泡排序 * @param a * @param n */ public static void bubleSort(int[] a,int n){ boolean flag = true; for (int i = 0; i <n&&flag ; i++) { flag=false; for (int j = 1; j <n-i ; j++) { if (a[j-1]<a[j]) { int tmp = a[j]; a[j]= a[j-1]; a[j-1]=tmp; flag=true; } } printArray(a,8); System.out.println(""); } } public static void printArray(int[] a,int n){ for (int i = 0; i <n ; i++) { System.out.print(a[i]+" "); } }