八大排序算法
直接插入排序
public static void insertSort(int[] arr){ for(int i = 1; i < arr.length; i++){ for(int j = i; j > 0; j--){ if(arr[j] < arr[j-1]){ int temp = arr[j]; arr[j] = arr[j-1]; arr[j-1] = temp; }else{ break; } } } }希尔排序
public void shellSort(int[] arr){ // knuth序列 int h = 1; while( h < arr.length/3){ h = h*3+1; } for(int gap = h; gap > 0; gap = (gap-1)/3){ //for(int gap = arr.length/2; gap > 0; gap /= 2){ for(int i = gap; i < arr.length; i++){ for(int j = i; j >= gap; j -= gap){ if(arr[j] < arr[j-gap]){ int temp = arr[j]; arr[j] = arr[j-gap]; arr[j-gap] = temp; }else{ break; } } } } } }选择排序
public static void selectSort(int[] arr){ for(int i = 0; i < arr.length-1; i++){ int index = i; for(int j = i+1; j < arr.length; j++){ if(arr[j] < arr[index]){ index = j; } } if(index != i){ int temp = arr[index]; arr[index] = arr[i]; arr[i] = temp; } } }堆排序
public static void heapify(int[] arr, int n, int i){ if(i >= n) return; int c1 = 2*i + 1; int c2 = 2*i + 2; int max = i; if(c1 < n && arr[c1] > arr[max]){ max = c1; } if(c2 < n && arr[c2] > arr[max]){ max = c2; } if(max != i){ int temp = arr[i]; arr[i] = arr[max]; arr[max] = temp; heapify(arr, n, max); } } public static void build_heap(int[] arr, int n){ int last_node = n-1; int parent = (last_node - 1)/2; for(int i = parent; i >= 0; i--){ heapify(arr, n, i); } } public static void heap_sort(int[] arr, int n){ // n表示arr数组的长度。 build_heap(arr, n); for(int i = n - 1; i >= 0; i--){ int temp = arr[i]; arr[i] = arr[0]; arr[0] = temp; heapify(arr, i, 0); } }冒泡排序
// 原始版冒泡排序 public static void bubble(int[] arr){ int n = arr.length; for(int i = 0; i < n-1; i++){ for(int j = 0; j < n-1-i; j++){ if(arr[j] > arr[j+1]){ int temp = arr[j]; arr[j] = arr[j+1]; arr[j+1] = temp; } } } } // 冒泡排序优化1 public void bubbule_1(int[] arr){ int n = arr.length; for(int i = 0; i < n-1; i++){ boolean flag = true; for(int j = 0; j < n - 1 -i; j++){ if(arr[j] > arr[j+1]){ int temp = arr[j]; arr[j] = arr[j+1]; arr[j+1] = temp; flag = false; } } if(flag){ break; } } } // 冒泡排序优化2 public void bubble_2(int[] arr){ int n = arr.length; int lastIndex = 0; int border = n-1; for(int i = 0; i < n-1; i++){ for(int j = 0; j < border; j++){ if(arr[j] > arr[j+1]){ int temp = arr[j]; arr[j] = arr[j+1]; arr[j+1] = temp; lastIndex = j; } } border = lastIndex; } } //冒泡排序优化3 鸡尾酒算法 public void bubble_3(int[] nums){ int n = nums.length; int leftBorder = 0; int rightBorder = n-1; int lastIndex = 0; int preIndex = 0; for(int i = 0; i < n/2 && leftBorder < rightBorder; i++){ for(int j = leftBorder; j < rightBorder; j++){ if(nums[j] > nums[j+1]){ int temp = nums[j]; nums[j] = nums[j+1]; nums[j+1] = temp; lastIndex = j; } } for(int j = rightBorder; j > leftBorder; j--){ if(nums[j] < nums[j-1]){ int temp = nums[j]; nums[j] = nums[j-1]; nums[j-1] = temp; preIndex = j; } } rightBorder = lastIndex; leftBorder = preIndex; } }快速排序
public static void quickSort(int[] nums, int left, int right){ if(left >= right){ return; } int low = left; int high = right; int pivot = nums[left]; while(left < right){ while(left < right && nums[right] > pivot){ right--; } nums[left] = nums[right]; while(left < right && nums[left] < pivot){ left++; } nums[right] = nums[left]; } nums[left] = pivot; quickSort(nums, low, left-1); quickSort(nums, left+1, high); }归并排序
public static void sort(int[] arr, int L, int R) { if(L == R) { return; } int mid = L + ((R - L) >> 1); sort(arr, L, mid); sort(arr, mid + 1, R); merge(arr, L, mid, R); } public static void merge(int[] arr, int L, int mid, int R) { int[] temp = new int[R - L + 1]; int i = 0; int p1 = L; int p2 = mid + 1; // 比较左右两部分的元素，哪个小，把那个元素填入temp中 while(p1 <= mid && p2 <= R) { temp[i++] = arr[p1] <= arr[p2] ? arr[p1++] : arr[p2++]; } // 上面的循环退出后，把剩余的元素依次填入到temp中 // 以下两个while只有一个会执行 while(p1 <= mid) { temp[i++] = arr[p1++]; } while(p2 <= R) { temp[i++] = arr[p2++]; } // 把最终的排序的结果复制给原数组 for(i = 0; i < temp.length; i++) { arr[L + i] = temp[i]; } }基数排序
//第一点：d表示1、10、100等，序列的最大值长度是2，d就是100。 private static void radixSort(int[] arr, int d) { int k = 0; int n = 1; int m = 1; int[][] temp = new int[10][arr.length]; int[] order = new int[10]; while(m <= d){ for(int i = 0; i < arr.length; i++){ int lsd = (arr[i] / n) % 10; temp[lsd][order[lsd]] = arr[i]; order[lsd]++; } for(int i = 0; i < 10; i++){ if(order[i] != 0){ for(int j = 0; j < order[i]; j++){ arr[k] = temp[i][j]; k++; } System.out.println("-----"); } order[i] = 0; } n *= 10; k = 0; m++; } }
