现在的位置: 主页 > 企业简介 > 文章列表

常见排序集合(冒泡排序,选择排序,直接插入排序,二

作者:程力专用汽车股份有限公司 来源:www.dfclxwc.com 未知发布时间:2017-09-09 10:30:14
常见排序集合(冒泡排序,选择排序,直接插入排序,二分插入排序,快速排序,希尔排序,归并排序)

一下是一些常见的排序算法:

交换元素(后面算法都有用到):

// 交换元素 private static void swap(int[] a, int i, int j) { int temp; temp = a[i]; a[i] = a[j]; a[j] = temp; }
冒泡排序(有优化): // 冒泡排序(优化①,②,③,④) private static void bubbleSort(int[] a) { boolean flag = false;// ①表示整个序列是无序的 for (int i = 0; i < a.length - 1; i++) { flag = true; // ②假设:此时序列是有序的 for (int j = 0; j < a.length - i - 1; j++) { if (a[j] > a[j + 1]) { swap(a, j, j + 1); flag = false;// ③只要出现了交换位置,则上面假设不成立 } } // ④上面假设成立(即序列有序),直接返回,不需要再循环冒泡了 if (flag) { return; } } }
选择排序: // 选择排序 private static void selectSort(int[] a) { for (int i = 0; i < a.length - 1; i++) { for (int j = i + 1; j < a.length; j++) { if (a[i] > a[j]) { swap(a, i, j); } } } } 直接插入排序: // 直接插入排序 private static void inserteSort(int[] a) { for (int i = 0; i < a.length - 1; i++) { int temp = a[i + 1]; int j = i; while (a[j] > temp) { a[j + 1] = a[j]; j--; if (j < 0) { break; } } a[j + 1] = temp; } } 二分插入排序: // 二分插入排序 private static void binaryInsertSort(int[] a) { for (int i = 0; i < a.length - 1; i++) { int low = 0; int high = i; int temp = a[i + 1]; int mid; // 在low和high之间的区域内进行二分法,以确定新元素的插入位置 while (low <= high) { mid = (low + high) / 2; if (a[mid] > temp) {// 若带插入的数小于中间元素a[mid],则目标落在左半区 high = mid - 1; } else {// r若带插入的数大于等于中间元素a[mid],则目标落于右半区 low = mid + 1; } } // 搜索的最后一个小区间的high位置(即是查找目标,因此新元素的插入位置(即high+1) // 把原来从high到i范围内的元素依次后移一个位置 for (int j = i; j > high; j--) { a[j + 1] = a[j]; } a[high + 1] = temp; } }
希尔排序: // 希尔排序 private static void shellSort(int[] a) { // 进行分组,初始步长设为数组长度的的一半(即n/2),然后依次减半,直到最后取1 for (int gap = (a.length + 1) / 2; gap > 0;) { // 组内排序 for (int i = 0; i < a.length - gap; i++) {// 定位到每一个元素 for (int j = i; j < a.length - gap; j += gap) { if (a[j] > a[j + gap]) { swap(a, j, j + gap); } } } // for循环修正 if (gap > 1) { gap = (gap + 1) / 2; } else if (gap == 1) { break; } } }
快速排序(优化): // 快速排序 private static void quickSort(int[] a, int l, int r) { if (l < r) { int p = partition(a, l, r); quickSort(a, l, p - 1); quickSort(a, p + 1, r); } } private static int partition(int[] a, int l, int r) { // 优化随机取枢轴 int rand = (int) (Math.random() * (r - l)); swap(a, l, l + rand); int i = l;// 第一个元素为枢轴 int j = r + 1; int x = a[i]; while (true) { while ((a[++i] < x) && i < r) { } ;// 定位指针i,找到比x大的元素 while ((a[--j] > x)) { } ; // 定位指针j if (i >= j) { break; } swap(a, i, j); } swap(a, l, j);// 枢轴a[l]要换到中间位置 return j; }

归并排序: // 归并排序 private static void mergeSort(int[] a, int l, int r) { if (l < r) {//至少两个元素 int mid = (r + l)/2; //把序列拆分成两个子序列[left,mid]和[mid+1,right] //同时还要对分解后的子序列分别进行递归“归并排序” mergeSort(a, l, mid); mergeSort(a, mid + 1, r); //把两个已经排好序的数组进行归并 int[] b = new int[a.length]; merge(a, b, l, mid, r); copyArray(a, b, l, r); } } private static void copyArray(int[] a, int[] b, int l, int r) { for(int i=l;i<=r;i++){ a[i]=b[i]; } } //把两个已经排好的子序列(a[letf,mid]he a[mid+1,right])合并成一个b[left,right] private static void merge(int[] a, int[] b, int left, int mid, int right) { int r=left; int p=mid+1; int k=left; while(r<=mid&&p<=right){ if(a[r]<=a[p]){ b[k++]=a[r++]; }else{ b[k++]=a[p++]; } } //此时,肯定有一个子序列中的元素全部移动到b[]数组中,因此,需要把未移完的子序列当中的所有剩余的元素直接拷到数组b[]中即可 if(r>mid){//左子序已经完成,因此剩下的是有序列,对拷有序列中的剩余元素即可 for(int i=p;i<=right;i++){ b[k++]=a[i]; } }else{//对拷左子序中的剩余元素 for(int i=r;i<=mid;i++){ b[k++]=a[i]; } } }


企业建站2800元起,携手武汉肥猫科技,做一个有见地的颜值派!更多优惠请戳:湖北网站制作 http://hubei.666rj.com

上一篇:php +ajax +sql 实现分页 下一篇:最后一页