java实现的9种排序
程序员文章站
2024-01-25 18:25:28
...
交换排序:
1.冒泡排序
2.快排
选择排序
1.直接选择
2.堆排序
插入排序
1.直接插入排序
2.折半插入排序
3.希尔排序
方法1.
方法2:
方法1和2的微妙之处,至于1是在span之内先增加i,遇到块便向后查询
2是先循环一个块上的数据来排序,然后在span之内在递增
二者最外层都是在缩小span;
解释的不是很清楚,需要阅读代码
其他:
归并排序
基数排序
暂无
本文参照了网上一些文章,对此如有版权问题,请与我联系,放在这里主要是为了共同学习。
1.冒泡排序
public static void bubble(int arr[]){ for(int i=1;i<arr.length;i++){//控制次数 for(int j=0;j<arr.length-i;j++){//控制当前比较到那个位置 if(arr[j]>arr[j+1]){ swap(arr,j,j+1); } } } }
2.快排
public static void quickSort(int a[],int left,int right){ int i; if(left<right){ i=partition(a,left,right); quickSort(a,left,i-1); quickSort(a,i+1,right); } } public static int partition(int a[],int left,int right){ int base = a[left]; while(left<right){ while(left<right && a[right]>=base) {--right;} a[left] = a[right]; while(left<right && a[left]<=base) {++left;} a[right] = a[left]; } a[left] = base;//a[right]=base; right==left; return left; }
选择排序
1.直接选择
public static void select(int a[]){ int index; for(int i=0;i<a.length-1;i++){ index = i; for(int j=i+1;j<a.length;j++){ if(a[j]<a[index]){ index = j; } } if(index!=i){ swap(a,index,i); } } }
2.堆排序
public static void heap(int[] data) { int n = data.length; for(int i=n/2-1;i>=0;i--){//从中间有叶子节点的数据开始 keepHeap(data,i,n); } while (n > 0) { swap(data, 0, n-1);//把第一个和本次建堆的最后一个交换 keepHeap(data, 0,--n);//排除最后一个继续建堆 } } /** * 建(大/小顶)堆操作 * @param r * @param index 本次建堆的起始下标 * @param length 本次建堆的数据长度 */ private static void keepHeap(int[] r, int index,int length) { int x = r[index]; int j = 2 * index + 1; while (j < length ) {//注意是: 下标 < 长度(不是 下标<最长的下表) if (j < length - 1 && r[j] < r[j + 1])//判断是否存在右节点,且和左节点比较大小 ++j; if (r[j] > x) { r[index] = r[j];//上面小的变成下面大的 index = j; j = 2 * index + 1; //继续向下 }else{ break; } } r[index] = x; }
插入排序
1.直接插入排序
public static void insert(int a[]){ for(int i=1;i<a.length;i++){ int t = a[i]; int j = i-1; while(j>=0 && t<a[j]){ a[j+1] = a[j]; j--; } a[j+1] = t; } }
2.折半插入排序
public static void halfInsert(int a[]){ for(int i=1;i<a.length;i++){ int t = a[i]; int big = i-1, small = 0; while(big>=small){ int mid = (big+small)/2; if(a[mid]<t){ small = mid+1; }else{ big = mid-1; } } //(i-1)->small 数值 均向前移动一位 for(int j=i;j>small;j--){ a[j] = a[j-1]; } a[big+1] = t; } }
3.希尔排序
方法1.
public static void shell(int a[]){ for(int span=a.length/2;span>=1;span--){ for(int i=span;i<a.length;i++){ int tmp = a[i]; int j = i-span; while(j>=0 && a[j]>tmp){ a[j+span] = a[j]; j -= span; } a[j+span] = tmp; } } }
方法2:
public static void shell2(Number[] data) { int span=data.length/7; if(span==0)span=1; while(span>=1){ for(int i=0;i<span;i++){ for(int j=i;j<data.length;j=j+span){ //组内直接插入排序 int p = j-span; Number temp = data[j]; while( p >=0 && data[p].doubleValue() > temp.doubleValue()){ data[p+span] = data[p]; p -=span; } data[p + span] = temp; } } span=span/2; } }
方法1和2的微妙之处,至于1是在span之内先增加i,遇到块便向后查询
2是先循环一个块上的数据来排序,然后在span之内在递增
二者最外层都是在缩小span;
解释的不是很清楚,需要阅读代码
其他:
归并排序
/** * 分治和归并 * @param a * @param low * @param high * @param b */ public static void mergeSort(int a[],int low,int high,int b[]){ int mid; if(low<high){ mid = (low+high)/2;//分治位置 mergeSort(a, low, mid, b); mergeSort(a,mid+1,high,b); merge(a,low,mid,high,b);//归并 } } /** * 合并两个有序子序列 * @param a * @param low * @param mid * @param high * @param b 辅助数组 */ public static void merge(int a[],int low,int mid,int high,int b[]){ int i = low; int j = mid+1; int p = 0; while(i<=mid&&j<=high){ b[p++] = (a[i]<=a[j])?a[i++]:a[j++]; } //如果子序列1没有合并完则直接复制到辅助数组中去 //复制low mid段未被copy的部分 while(i<=mid){ b[p++] = a[i++]; } //如果子序列2没有合并完则直接复制到辅助数组中去 //复制mid+1 high段未被copy的部分 while(j<=high){ b[p++] = a[j++]; } //把辅助数组的元素复制到原来的数组中去 //复制b[0 ~ p-1]到a[low ~ high] for(p=0,i=low;i<=high;i++,p++){ a[i] = b[p]; } }
基数排序
暂无
本文参照了网上一些文章,对此如有版权问题,请与我联系,放在这里主要是为了共同学习。