冒泡排序:
public static void bubbleSort(int[] array){ int temp = 0; for(int i = 0; i < array.length; i++){ for(int j = 0; j < array.length - i - 1; j++){ if(array[j] > array[j+1]){ temp = array[j]; array[j] = array[j+1]; array[j+1] = temp; } } } }
选择排序:
public static void selectSort(int[] input){ for(int i = 0; i < input.length; i++){ int index = i; for(int j = i+1; j < input.length; j++){ if(input[index]>input[j]){ index = j; } } if(index != i){ int temp = input[i]; input[i] = input[index]; input[index] = temp; } } }
shell排序
void shellSort(int[] a){ int i,j,h; int r,temp; int x=0; for(a.length/2;r>=1;r/=2){ for(i=r;i<a.length;i++){ temp=a[i]; j=i-r; while(j>=0&&temp<a[j]){ a[j+r]=a[j]; j-=r; } a[j+r]=temp; } x++; } }
快速排序
void quickSort(int[] arr,int left,int right){ int f,t; int rtemp,ltemp; ltemp=left; rtemp=right; f=arr[(left+right)/2]; while(ltemp<rtemp){ while(arr[ltemp]<f){ ++ltemp; } while(arr[rtemp]>f){ --rtemp; } if(ltemp<=rtemp){ t=arr[ltemp]; arr[ltemp]=arr[rtemp]; arr[rtemp]=t; --rtemp; ++ltemp; } } if(ltemp==rtemp){ ltemp++; } if(left<rtemp){ quickSort(arr,left,ltemp-1); } if(ltemp<right){ quickSort(arr,rtemp+1,right); } }
基数排序:
private static void radixSort(int[] array,int d){ int n=1; //代表位数对应的数:1,10,100... int k=0; //保存每一位排序后的结果用于下一位的排序输入 int length=array.length; //排序桶用于保存每次排序后的结果,这一位上排序结果相同的数字放在同一个桶里 int[][] bucket=new int[10][length]; int[] order=new int[length];//用于保存每个桶里有多少个数字 while(n < d){ for(int num:array){ int digit=(num/n)%10; bucket[digit][order[digit]]=num; order[digit]++; } //将前一个循环生成的桶里的数据覆盖到原数组中用于保存这一位的排序结果 for(int i = 0; i < length; i++){ //这个桶里有数据,从上到下遍历这个桶并将数据保存到原数组 if(order[i] != 0){ for(int j = 0; j < order[i]; j++){ array[k] = bucket[i][j]; k++; } } order[i]=0;//将桶里计数器置0,用于下一次位排序 } n*=10; k=0;//将k置0,用于下一轮保存位排序结果 } }
计数排序:
/** *计数排序:下面博客地址讲解的超级详细 *http://www.cnblogs.com/kaituorensheng/archive/2013/02/23/2923877.html **/ public static void countsort(int[] input, int[] output, int k) { // input为输入数组,output为输出数组,k表示有所输入数字都介于0到k之间(包含k) int[] c = new int[k];// 临时存储区 int len = c.length; // 初始化 for (int i = 0; i < len; i++) { c[i] = 0; } // 检查每个输入元素,如果一个输入元素的值为input[i],那么c[input[i]]的值加1, //此操作完成后,c[i]中存放了值为i的元素的个数 for (int i = 0; i < input.length; i++) { c[input[i]]++; } // 通过在c中记录计数和,c[i]中存放的是小于等于i元素的数字个数 for (int i = 1; i < len; i++) { c[i] = c[i] + c[i - 1]; } // 把输入数组中的元素放在输出数组中对应的位置上 for (int i = input.length - 1; i >= 0; i--) {// 从后往前遍历 output[c[input[i]] - 1] = input[i]; c[input[i]]--;// 该操作使得下一个值为input[i]的元素直接进入输出数组中input[i]的前一个位置 } }
归并排序:
public class Test { public static void main(String[] args) { int[] ia = {4,8,9,5,2,1,4,6}; mergeSort(ia, 0, ia.length-1); for(int i : ia){ System.out.print(i +" "); } } public static void mergeSort(int[] a, int low, int high){ if(low < high){ mergeSort(a, low, (high + low)/2); mergeSort(a, (low + high)/2+1, high); merge(a,low, (high + low)/2, high); } } //将连个数组合并成一个数组 public static void merge(int[] a,int p,int q,int r){ int[] b = new int[r-p+1]; int s = p; int t = q+1; int k = 0; while(s <= q && t <= r){ if(a[s] < a[t]){ b[k++] = a[s++]; }else{ b[k++] = a[t++]; } } while(s <= q){ b[k++] = a[s++]; } while(t <= r){ b[k++] = a[t++]; } for(int i = 0; i < b.length; i++){ a[p+i] = b[i]; } } }
堆排序:
public class MaxHeap { int[] heap; int heapsize; public MaxHeap(int[] array){ this.heap=array; this.heapsize=heap.length; } public void buildMaxHeap(){ for(int i=heapsize/2-1;i>=0;i--){ maxify(i);//依次向上将当前子树最大堆化 } } public void heapSort(){ for(int i=0;i<heap.length;i++){ //执行n次,将每个当前最大的值放到堆末尾 int tmp=heap[0]; heap[0]=heap[heapsize-1]; heap[heapsize-1]=tmp; heapsize--; maxify(0); } } public void maxify(int i){ int l=left(i); int r=right(i); int largest; if(l<heapsize&&heap[l]>heap[i]) largest=l; else largest=i; if(r<heapsize&&heap[r]>heap[largest]) largest=r; if(largest==i||largest>=heapsize)//如果largest等于i说明i是最大元素 largest超出heap范围说明不存在比i节点大的子女 return ; int tmp=heap[i];//交换i与largest对应的元素位置,在largest位置递归调用maxify heap[i]=heap[largest]; heap[largest]=tmp; maxify(largest); } public void increaseValue(int i,int val){ heap[i]=val; if(i>=heapsize||i<=0||heap[i]>=val) return; int p=parent(i); if(heap[p]>=val) return; heap[i]=heap[p]; increaseValue(p, val); } private int parent(int i){ return (i-1)/2; } private int left(int i){ return 2*(i+1)-1; } private int right(int i){ return 2*(i+1); } } public class Demo { public static void main(String[] args){ int[] array = new int[]{1,2,3,4,7,8,9,10,14,16}; MaxHeap heap = new MaxHeap(array); System.out.println("构造一个堆的结构:"); printHeapTree(heap.heap); heap.buildMaxHeap(); System.out.println("执行最大堆化后堆的结构:"); printHeapTree(heap.heap); heap.heapSort(); System.out.println("执行堆排序后数组的内容"); printHeap(heap.heap); } /** 打印已经构造好的堆 */ private static void printHeapTree(int[] array){ for(int i = 1; i < array.length; i = i*2){ for(int k = i-1; k < 2*(i)-1 && k < array.length; k++){ System.out.print(array[k]+" "); } System.out.println(); } } /** 输出调整好后的堆 */ private static void printHeap(int[] array){ for(int i = 0; i < array.length; i++){ System.out.print(array[i]+" "); } } }
相关推荐
本资源总结了在java中出现的各种排序方法
java的各种排序方法的总结,有助于加深对排序的理解
常用排序算法总结常用排序算法总结常用排序算法总结常用排序算法总结常用排序算法总结常用排序算法总结常用排序算法总结常用排序算法总结常用排序算法总结常用排序算法总结
所谓排序,就是使一串记录,按照其中的某个或某些关键字的大小,递增或递减的排列起来的操作。...在各个领域中考虑到数据的各种限制和规范,要得到一个符合实际的优秀算法,得经过大量的推理和分析。
qsort总结.pdf快速排序总结qsort总结.pdf快速排序总结qsort总结.pdf快速排序总结 还有实现代码
常见的排序算法进行整理,包括:插入排序、选择排序、冒泡排序、快速排序、堆排序、归并排序、希尔排序、二叉树排序、计数 排序、桶排序、基数排序。
堆排序总结.doc 堆排序总结.doc 堆排序总结.doc 堆排序总结.doc
数据结构各种算法总结,冒泡法等排序算法的比较,有助于更深刻的理解
常用排序算法总结,包括插入排序(InsertionSort),冒泡排序(BubbleSort),选择排序(SelectionSort),快速排序(QuickSort), * 二路归并排序(MergeSort),堆排序(HeapSort)。有每一种排序算法的复杂度分析以及实现...
排序算法总结和比较 介绍各种排序算法的特点及原理,大致总结了我们常见的所有的排序算法的特点
深入浅出的全面介绍 精妙总结 可以把握与运用排序
各种排序算法的稳定性和时间复杂度总结。希望大家能有所收获。
各种排序算法的总结和比较 非常实用 希望大家喜欢
C#排序算法总结:交换排序:最基础的冒泡排序,冒泡排序的优化版选择排序和快速排序,插入排序:直接插入排序和折半插入排序。
排序算法总结.doc 排序算法总结.doc 排序算法总结.doc
总结了各种排序算法,并用C++代码实现,并有演示
八大排序算法总八大排序算法总八大排序算法总八大排序算法总结
查找與排序 查找與排序 查找與排序 查找與排序 查找與排序 查找與排序
排序学习总结. 排序学习总结. 排序学习总结. 排序学习总结.