package codingforoffer.question08; import java.util.ArrayList; import java.util.Arrays; public class SearchAndSort { /** * 插入排序 */ public static int[] insert(int[] arr){ for (int i = 1; i < arr.length; i++) { int k=arr[i]; int j=i-1; while(j>=0 && k<arr[j]){ arr[j+1]=arr[j]; j--; } arr[j+1]=k; } return arr; } /** * 冒泡排序 * @param args */ public static int[] bubble(int[] arr){ for (int i = 0; i < arr.length; i++) { for (int j = 0; j < arr.length-i-1; j++) { if(arr[j]>arr[j+1]){ int temp=arr[j]; arr[j]=arr[j+1]; arr[j+1]=temp; } } } return arr; } /** * 快速排序,使用了分治策略的思想,根据数组最后一个元素的大小，将数组分开 * @param args */ public static void quickSort(int[] arr,int low,int high){ if(low<high){ int q=quick(arr,low,high); quickSort(arr, low, q); quickSort(arr, q+1, high); } } /** * 求出末尾角标值 * @param arr * @param low * @param high * @return */ private static int quick(int[] arr,int low,int high) { //含左不含右 // TODO Auto-generated method stub int k=arr[high-1];//最后一个元素 int j=low; //指向大于k的最小角标 for (int i = low; i < high-1; i++) { if(arr[i]<k){ // int temp=arr[j]; arr[j]=arr[i]; arr[i]=temp; j++; } } arr[high-1]=arr[j]; arr[j]=k; return j; } /** * 归并算法 * @param args */ public static void mergeSort(int[] arr,int low,int high){ if(low<high && low!=high-1){ int p=(low+high)/2; mergeSort(arr, low, p); mergeSort(arr, p, high); merge(arr,p,low,high); } } public static void merge(int[] arr, int p, int low, int high){ //含左不含右 int[] arrlow=new int[p-low+1]; //最后加个标记无穷大 int[] arrhigh=new int[high-p+1]; int[] newArr=new int[high-low]; for (int i = low; i < p; i++) { arrlow[i-low]=arr[i]; } arrlow[p-low]=Integer.MAX_VALUE; for (int i = p; i < high; i++) { arrhigh[i-p]=arr[i]; } arrhigh[high-p]=Integer.MAX_VALUE; int i=0; int j=0; int k=0; while(k<newArr.length){ if(arrlow[i]<arrhigh[j]){ newArr[k++]=arrlow[i++]; }else{ newArr[k++]=arrhigh[j++]; } } for (int k2 = 0; k2 < newArr.length; k2++) { //排好序的放到arr里面 arr[k2+low]=newArr[k2]; } } public static void main(String[] args) { int[] arr={3,2,5,2,4,3,9,3,2,34,3,55,4345}; // int[] result = insert(arr);//插入排序 mergeSort(arr,0,arr.length); for (int i = 0; i < arr.length; i++) { System.out.println(arr[i]); } } }
选择排序：
/** * 选择排序：每次从剩余的数组中选择一个最小的数，依次放到前面的数组中（每次进行交换一次）。 * @param arr */ public void selectSort(int[] arr) { int mindex; for (int i = 0; i < arr.length-1; i++) { mindex=i; for (int j = i+1; j < arr.length; j++) { if (arr[j] < arr[mindex]) { mindex=j; } } int temp=arr[i]; arr[i]=arr[mindex]; arr[mindex]=temp; } }
堆排序：
package com.li.chapter06; import java.util.Arrays; import java.util.stream.IntStream; /** * 最大堆 */ public class Heapify { public static void main(String[] args){ Heapify heapify=new Heapify(); int[] arr = {2, 3, 4, 32, 2, 54, 7, 32, 20}; // int[] arr = {4, 3, 5}; heapify.buildMaxHeapify(arr); IntStream stream = Arrays.stream(arr); stream.forEach(System.out::println); System.out.println("堆排序"); heapify.heapSort(arr); IntStream stream1 = Arrays.stream(arr); stream1.forEach(System.out::println); } /** * 最大堆的角标值 */ public int parent(int i) { return (int) Math.floor(i / 2); //返回父节点的角标值 } //左孩子 public int leftChild(int i) { return 2*i+1; } //右孩子 public int rightChild(int i) { return 2*i+2; } /** * 维护最大堆的性质,使用一个数组模仿最大堆 */ public void maxHeapify(int[] arr, int i) { int largest; int l = leftChild(i); int r = rightChild(i); if (l<arr.length&&arr[i] < arr[l]) { largest=l; }else { largest=i; } if (r<arr.length&&arr[largest] < arr[r]) { largest=r; } if (largest != i) { int temp = arr[i]; arr[i] = arr[largest]; arr[largest]=temp; maxHeapify(arr,largest); } } /** * 构建最大堆 */ public void buildMaxHeapify(int[] arr) { for (int i = arr.length/2-1; i >=0; i--) { maxHeapify(arr, i); } } /** * 堆排序算法 */ public void heapSort(int[] arr) { int heapSize=arr.length; buildMaxHeapify(arr); for (int i=arr.length/2;i>=1;i--) { int temp=arr[1]; arr[1] = arr[i]; arr[i]=temp; heapSize=heapSize-1; maxHeapify(arr,1); } } /** * 优先队列,最大值 */ public int heapMaximum(int[] arr) { return arr[1]; } /** * 提取最大值之后的维护 */ public int heapExtractMax(int[] arr) { int heapSize=arr.length; if (arr.length < 1) { throw new IndexOutOfBoundsException("heap 堆溢出"); } int max = arr[1]; arr[1] = arr[arr.length - 1]; heapSize=heapSize-1; maxHeapify(arr,1); return max; } /** * 第i个元素换为key */ public void heapIncreaseKey(int[] arr, int i, int key) throws InterruptedException { if(key<arr[i]){ throw new InterruptedException("新的key小于当前值"); } arr[i]=key; while(i>1&&arr[parent(i)]<arr[i]){ int temp = arr[i]; arr[i] = arr[parent(i)]; arr[parent(i)]=temp; i = parent(i); } } }
稳定排序：保证排序前两个相等的数，排序后顺序和排序前顺序相同。例如在排序前A[i]=A[j]， 且A[i]在A[j]前面，那么排序后A[i]也应该在A[j]前面。改排序算法就是稳定的。
参考：http://www.cnblogs.com/gaochundong/p/comparison_sorting_algorithms.html