首页 > 代码库 > 基本排序算法（冒泡排序 选择排序 插入排序 快速排序 归并排序 基数排序 希尔排序）
基本排序算法（冒泡排序 选择排序 插入排序 快速排序 归并排序 基数排序 希尔排序）
冒泡排序
public static void bubbleSort(int[] arr){ int lgn = arr.length; for (int i = 0; i < lgn - 1; i++) { for (int j = 0; j < lgn - 1 - i; j++) { if(arr[j] > arr[j + 1]){ int temp = arr[j + 1]; arr[j + 1] = arr[j]; arr[j] = temp; } } } }
选择排序
public static void SelectionSort(int[] arr){ for (int i = 0; i < arr.length; i++) { for (int j = i + 1; j < arr.length ; j++) { if(arr[j] < arr[i]){ int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } } } }
插入排序
public static void insertionSort(int [] array){ for(int i = 1; i < array.length; i++){ int temp = array[i];//被标记的值或者说是当前需要插入的值 int j = i; //如果轮循值大于被标记值则往后移 while( j > 0 && temp < array[j - 1]){ array[j] = array[j - 1]; j-- ; } //将被标记值插入最终移出的空位置 array[j] = temp; } }
快速排序
public static void quikeSort(int[] arr, int low, int high) { int start = low; int end = high; int anchor = arr[low]; while (end > start) { //比较 anchor---end while (end > start && arr[end] >= anchor) { //从末尾向前寻找小于等于anchor的值 end--; } //交换位置 if (arr[end] <= anchor) { int temp = arr[end]; arr[end] = arr[start]; arr[start] = temp; } //比较start---anchor while (end > start && arr[start] <= anchor) {//从起始位置向后寻找大于等于anchor的值 start++; } //交换位置 if (arr[start] >= anchor) { int temp = arr[start]; arr[start] = arr[end]; arr[end] = temp; } } //anchor位置确定。左边的元素值都小于anchor值，右边的值都大于anchor值，递归排序左右两侧排序 //左边元素。low---anchor值索引-1 if (start > low) { quikeSort(arr, low, start - 1); } //右边元素。从anchor值索引+1---high if (end < high) { quikeSort(arr, end + 1, high); } }
归并排序
public static void mergeSort(int[] data) { sort(data, 0, data.length - 1); } public static void sort(int[] data, int left, int right) { if (left >= right) return; // 找出中间索引 int center = (left + right) / 2; // 对左边数组进行递归 sort(data, left, center); // 对右边数组进行递归 sort(data, center + 1, right); // 合并 merge(data, left, center, right); } /** * 将两个数组进行归并，归并前面2个数组已有序，归并后依然有序 * * @param data * 数组对象 * @param left * 左数组的第一个元素的索引 * @param center * 左数组的最后一个元素的索引，center+1是右数组第一个元素的索引 * @param right * 右数组最后一个元素的索引 */ public static void merge(int[] data, int left, int center, int right) { // 临时数组 int[] tmpArr = new int[data.length]; // 右数组第一个元素索引 int mid = center + 1; // third 记录临时数组的索引 int third = left; // 缓存左数组第一个元素的索引 int tmp = left; while (left <= center && mid <= right) { // 从两个数组中取出最小的放入临时数组 if (data[left] <= data[mid]) { tmpArr[third++] = data[left++]; } else { tmpArr[third++] = data[mid++]; } } // 剩余部分依次放入临时数组（实际上两个while只会执行其中一个） while (mid <= right) { tmpArr[third++] = data[mid++]; } while (left <= center) { tmpArr[third++] = data[left++]; } // 将临时数组中的内容拷贝回原数组中 // （原left-right范围的内容被复制回原数组） while (tmp <= right) { data[tmp] = tmpArr[tmp++]; } }
基数排序
//LSD public static void radixLSDSort(int[] arr){ //最高位数 int maxBit = getMaxBit(arr); //十个bulk 分别存放 每个位数 数字 相应的元素 如个位为3 则放入bulk[3] Queue<Integer>[] bulk = new Queue[10]; for (int i = 0; i < bulk.length; i++) { bulk[i] = new ArrayDeque(); } //分别处理不同位数 存放 处理 for (int i = 0; i < maxBit; i++) { for (int j = 0; j < arr.length; j++) { int ivalue = http://www.mamicode.com/(int) (arr[j] % Math.pow(10, i + 1) / Math.pow(10, i)); //去相应位数上的数字作为 存入bulk index bulk[ivalue].offer(arr[j]); } //取出bulk中的元素 重新放入数组 并清除bulk中的元素。 int arrIndex = 0; for (int j = 0; j < bulk.length; j++) { while (bulk[j].size()>0){ arr[arrIndex++] = bulk[j].poll(); } } } } public static int getMaxBit(int[] arr){ int max = arr[0]; for (int i = 1; i < arr.length; i++) { if(arr[i] > max){ max = arr[i]; } } int b = 0; while (max > 0){ max /= 10; b++; } return b; } public static void radixMSDSort(int[] arr){ msdSort(arr, 0, arr.length, getMaxBit(arr)); } //MSD public static void msdSort(int[] arr, int left, int right, int maxBit){ //十个bulk 分别存放 每个位数 数字 相应的元素 如个位为3 则放入bulk[3] Queue<Integer>[] bulk = new Queue[10]; for (int i = 0; i < bulk.length; i++) { bulk[i] = new ArrayDeque(); } //依据最高位分别放入不同的bulk for (int j = left; j < right; j++) { int ivalue = http://www.mamicode.com/(int) (arr[j] % Math.pow(10, maxBit) / Math.pow(10, maxBit - 1)); //去相应位数上的数字作为 存入bulk index bulk[ivalue].offer(arr[j]); } //取出bulk中的元素 重新放入数组 并清除bulk中的元素。记录bulk中queue大小大于1的数组索引 递归使用 List<Integer> count = new ArrayList<Integer>(); int arrIndex = left; for (int j = 0; j < bulk.length; j++) { int start = arrIndex; while (bulk[j].size()>0){ arr[arrIndex++] = bulk[j].poll(); } if(arrIndex - start > 1){ count.add(start); count.add(arrIndex); } } //递归最小位判断 int nextBit = maxBit - 1; if(nextBit > 0) { for (int i = 1; i < count.size(); i += 2) { msdSort(arr, count.get(i - 1), count.get(i), nextBit); } } }
shell排序
public static void shellSort(int[] arr){ int step = arr.length/2; while (step >= 1) { //步长为1时 包含所有数组序列 for (int i = 0; i < step; i++) { //步长为n则数组将分为n组分别排序 for (int j = step + i; j < arr.length; j += step) { //对跨步长每组元素进行插入排序 int temp = arr[j]; int preIndex = j - step; while (preIndex > -1 && temp < arr[preIndex]) { arr[preIndex + step] = arr[preIndex]; preIndex -= step; } arr[preIndex + step] = temp; System.out.println(" middle: " + Arrays.toString(arr)); } } step /= 2; //每次步长处理 } }
基本排序算法（冒泡排序 选择排序 插入排序 快速排序 归并排序 基数排序 希尔排序）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。