浏览 3563 次
|
锁定老帖子 主题：JAVA各种排序思想和示例
精华帖 (0) :: 良好帖 (0) :: 新手帖 (0) :: 隐藏帖 (0)
|
|||||||||||||||||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 作者 | 正文 | ||||||||||||||||||||||||||||||
|
发表时间：2014-07-08
最后修改：2014-07-11
JAVA里面几种排序算法的原理
package com.sanjiesanxian.sort.test;
/**
* 所有排序算法的集合
* **/
public class AllSort {
static int datas[] = { 5, 2, 1, 3, 6,100,0,-9,999,12 };
public static void main(String[] args) {
// bubbleSort();
// selectSort();
//insertSort();
// / print("打印数组", datas);
//shellSort1(datas, datas.length);
//quickSort(datas, 0, datas.length-1);
//print("\n打印数组", datas);
}
/**
* @param a 待排序的数组
* @param n 数组的长度
*
* **/
public static void shellSort1(int []a,int n){
//gap为步长，每次减为原来的一半
for(int gap=n/2;gap>0;gap/=2){
//共有gap个组,对每一个组都执行直接插入排序
for(int i=0;i<gap;i++){
for(int j=i+gap;j<n;j+=gap){
//如果a[j]<a[j-gap].则寻找a[j]位置，并将后面的数据的位置都后移
if(a[j]<a[j-gap]){
int tmp=a[j];
int k=j-gap;
while(k>=0&&a[k]>tmp){
a[k+gap]=a[k];
k-=gap;
}
a[k+gap]=tmp;
}
}
}
}
}
/**
*
* 对希尔排序中的单个组进行排序
*
* @param a 待排序的数组
* @param n 数组总的长度
* @param i 组的起始位置
* @param gap 组的增量间隔
*
*拆开2个方法
*
* **/
public static void groupSort(int[] a,int n,int i,int gap){
for(int j=i+1;j<n;j+=gap){
//如果a[j]<a[j-gap].则寻找a[j]位置，并将后面的数据的位置都后移
if(a[j]<a[j-gap]){
int tmp=a[j];
int k=j-gap;
while(k>=0&&a[k]>tmp){
a[k+gap]=a[k];
k-=gap;
}
a[k+gap]=tmp;
}
}
}
/**
* 希尔排序，拆分版
* @param a 待排序的数组
* @param n 数组的长度
*
* */
public static void shellSort2(int []a ,int n){
//gap为增量，每次减少为原来的一半
for(int gap=n/2;gap>0;gap/=2){
//共gap个组，对每一组都执行直接插入排序
for (int i = 0; i < gap; i++) {
groupSort(a, n, i, gap);
}
}
}
/**
* 冒泡排序
*
* 排序原理： 通过两层循环控制， 外层循环，控制查找第i层的数，在余下的数据里最小或最大的
* 内层循环，负责依次比较下标相邻的两个数的大小，并负责将小数或大数的位置替换
*
* 每次的比较，都是上次在内存中替换完的新数组比较
*
* **/
public static void bubbleSort() {
System.out.print("排序前： ");
for (int t : datas) {
System.out.print(t + " ");
}
System.out.println();
for (int i = 0; i < datas.length; i++) {
for (int j = i + 1; j < datas.length; j++) {
int temp = 0;
System.out.println("i=" + i + " datas[i]=" + datas[i] + " , "
+ "j=" + j + " datas[j]=" + datas[j]);
if (datas[i] > datas[j]) {
temp = datas[j];
datas[j] = datas[i];
datas[i] = temp;
}
System.out.print("数组内容: ");
for (int t : datas) {
System.out.print(t + " ");
}
System.out.println("");
}
System.out.println("\n===========外部下面=============");
for (int t : datas) {
System.out.print(t + " ");
}
System.out.println("");
}
// System.out.print("排序后： ");
// for(int t:datas){
// System.out.print(t+" ");
// }
}
/**
*
* 快速排序的原理
*
* 对于一个数组，进行按照某个key值进行拆分，
* key值左边的数，统一小于key，key值右边统一大于key
* 然后递归对两边的的数组进行排序，
* 最后结果整体有序
*
* 怎么找到某个key值的点，默认按照取最后一个的数值来进行划分
*
*
*
*
*
*
* 快速排序
* @param arr 要排序的数组
* @param from 开头
* @param to 结尾
*
* **/
public static void quickSort(int arr[],int from ,int to){
//1,5,2,4
if(from<to){//仅当form<to时，才进行排序
int temp=arr[to];//temp等于数组最后一位数字
int i=from-1;//i等于-1；
for(int j=from;j<to;j++){//j=0；j小于最大的长度to，j++
if(arr[j]<=temp){//如果arr[j]的元素小于等于最后一位 数字
i++;//i++；0
int tempValue=arr[j];
arr[j]=arr[i];
arr[i]=tempValue;
}
// print("\n循环中的 ", arr);
}
arr[to]=arr[i+1];
arr[i+1]=temp;
//System.out.println("轴的位置: "+arr[i]);
quickSort(arr, from, i);
quickSort(arr, i+1, to);
}
}
/**
* 打印排序
* **/
public static void print(String info, int datas[]) {
System.out.print(info + ": ");
for (int i : datas) {
System.out.print(i + " ");
}
}
/**
* 选择排序
*
* 对比数组中前一个元素跟后一个元素的大小， 如果后面的元素比前面的元素小则用一个变量k来记住他的位置，
* 接着第二次比较，前面“后一个元素”现变成了“前一个元素”， 继续跟他的“后一个元素”进行比较如果后面的元素比他要小则用变量
* k记住它在数组中的位置(下标)，等到循环结束的时候，我们应该找到了最 小的那个数的下标了，然后进行判断，如果这个元素的下标不是第一个元素的下标，
* 就让第一个元素跟他交换一下值，这样就找到整个数组中最小的数了。然后找到数组中 第二小的数，让他跟数组中第二个元素交换一下值，以此类推。
*
*
* a）第一次循环：记录第一个数的下标 b）将第一个数的值与后面的值相比、如果比后面值大、则将下标值改为后面值所对应的下标。 c）
* 第一次循环结束后、如果下标值有改动、说明后面有比此数值小的元素、交换两者位置 d）重复上述操作、直到所有数值都已排序
*
*
*
*
*
* **/
public static void selectSort() {
print("排序前", datas);
for (int i = 0; i < datas.length; i++) {
int lowIndex = i;// 最小值的下标
for (int j = i + 1; j < datas.length; j++) {
if (datas[j] < datas[lowIndex]) {
lowIndex = j;
}
}
// 当lowindex的值与i的不一致时，就进行交换
if (lowIndex != i) {
int temp = datas[i];
datas[i] = datas[lowIndex];// 找到最小值付给当前的值
datas[lowIndex] = temp;// 最小值下标的等于
}
// print("\n排序", datas);
}
print("\n排序后", datas);
}
/**
* 插入排序 基本思想：在要排序的一组数中，假设前面(n-1) [n>=2] 个数已经是排
* 好顺序的，现在要把第n个数插到前面的有序数中，使得这n个数
* 也是排好顺序的。如此反复循环，直到全部排好顺序。
*
*
*
* **/
public static void insertSort() {
print("插入排序前: ", datas);
for (int i = 0; i < datas.length; i++) {
// 取出当前要插入的值
int insertVal = datas[i];
// 拿当前要插入的值和前一位比，一直比到第一位
int index = i - 1;
while (index >= 0 && datas[index] > insertVal) {
// 如果插入的值比前一位小，则将前一位的值，赋给插入位置，再拿当前值，和前一位比
//每次迭代都把最小的值放在前面
datas[index + 1] = datas[index];
index--;
}
datas[index + 1] = insertVal;
print("\n排序中: ", datas);
}
print("\n插入排序后: ", datas);
}
}
package com.sanjiesanxian.sort.test;
/**
* 桶排序
*
* */
public class BucketSort {
/**
* 桶排序
* @param a 待排序数组
* @param max 数组a中最大值的范围
* **/
public static void bucketSort(int[] a,int max){
int buckets[];
if(a==null||max<1){
return;
}
//创建一个为max的数组buckets，并且将buckets中所有数据初始化为0
buckets=new int[max];
//1，计数
for(int i=0;i<a.length;i++){
buckets[a[i]]++;
}
//排序
for(int i=0,j=0;i<max;i++){
while((buckets[i]--)>0){
a[j++]=i;
}
}
buckets=null;
}
public static void print(String info,int a[]){
System.out.print(info);
for(int aa:a){
System.out.print(aa+" ");
}
System.out.println();
}
public static void main(String[] args) {
//不支持负数排序
int a[]={1,5,2,88,9};
print("排序前: ", a);
bucketSort(a, 89);
print("排序后: ", a);
}
}
package com.sanjiesanxian.sort.test;
/**
* 堆排序
*
* **/
public class HeapSort {
/**
* 最大堆的向下调整算法
*
* 数组实现的堆中，第N个节点左孩子的索引值是2N+1，右孩子的索引值是2N+2
* 其中，N为数组下标索引值，如数组中第一个数对应的N为0
*
* @param a 待排序的数据
* @param start 被下调节点的起始位置 一般从0开始，表示从第一个开始
* @param end 截至范围一般为数组中最后一个元素索引
*
* **/
public static void maxHeapDown(int []a ,int start,int end){
int c=start; //当前节点的位置
int l=2*c+1; //左孩子的位置
int tmp=a[c]; //当前节点的大小
for(;l<=end;c=l,l=2*l+1){
//l 是左孩子，l+1是右孩子
if(l<end&&a[l]<a[l+1]){//最大堆
// if(l<end&&a[l]>a[l+1]){//最小堆
l++; //左右两孩子里面选择较大者，即为_heap[l+1]
}
if(tmp>a[l]){//最大堆
//if(tmp<=a[l]){//最小堆
break;
}else{
a[c]=a[l];
a[l]=tmp;
}
}
}
/**
* 堆排序从小到大
*
* @param a 排序的数组
* @param n 数组的长度
*
* */
public static void heapSortAsc(int [] a,int n){
int i,tmp;
//从(n/2-1)--->0逐次遍历，遍历之后，得到的数组，实际上是一个最大的二叉堆
for(i=n/2-1;i>=0;i--){
maxHeapDown(a, i, n-1);
}
//从最后一个元素开始对序列，进行调整，不断的缩小调整的范围，知道第一个元素
for(i=n-1;i>0;i--){
//交换a[0]和a[i],交换后a[i]是0....i中最大的
tmp=a[0];
a[0]=a[i];
a[i]=tmp;
//调整a[0.....i-1],使得a[0....i-1]中最大的
//即,保证a[i-1]是[0...i-1]中最大的值
maxHeapDown(a, 0, i-1);
}
}
public static void main(String[] args) {
int i;
int a[] = {1,4,-2,2,7,0,5};
print("排序前:", a);
heapSortAsc(a, a.length);//升序排列
print("排序后:", a);
}
public static void print(String info,int a[]){
System.out.print(info);
for(int aa:a){
System.out.print(aa+" ");
}
System.out.println();
}
}
package com.sanjiesanxian.sort.test;
/**
*
* 归并排序
*
* */
public class MergeSort {
/**
* 将一个数组中两个相邻有序的区间合并成一个
*
* @param a 包含有序区间的数组
* @param start 第一个有序区间的开始地址
* @param mid 第一个有序区间的结束地址，也是第二个有序区间的开始地址
* @param end 第二个有序区间的结束地址
*
* */
public static void merge(int []a,int start,int mid,int end){
int []temp=new int[end-start+1];
int i=start; //第一个有序区索引
int j=mid+1; //第二个有序区的索引
int k=0; //临时区域的索引
while(i<=mid&&j<=end){
if(a[i]<=a[j]){
temp[k++]=a[i++];
}else{
temp[k++]=a[j++];
}
}
while(i<=mid){
temp[k++]=a[i++];
}
while(j<=end){
temp[k++]=a[j++];
}
for(i=0;i<k;i++){
a[start+i]=temp[i];
}
temp=null;
}
/**
* 归并排序从上向下
*
* a待排序的数组
* start数组的起始地址
* end 数组的结束地址
*
* */
public static void mergeSortUp2Down(int []a,int start,int end){
if(a==null||start>=end){
return;
}
int mid=(end+start)/2;
mergeSortUp2Down(a, start, mid);//递归排序a[start...mid]
mergeSortUp2Down(a, mid+1, end);//递归排序a[mid+1...end]
//a[start...mid] 和 [mid+1...end] 两个有序空间
//将他们排序成一个有序的空间a[start....end]
merge(a, start, mid, end);
}
/***
* 对数组a做若干次合并: 数组a的总长度为len，将它分为若干个长度为gap的子数组；
* 将每2个相邻的子数组，进行合并排序
*
* @param a 待排序的数组
* @param len 数组的长度
* @param gap 子数组的长度
* **/
public static void mergeGroups(int []a,int len,int gap){
int i;
int twolen=2*gap; //两个相邻子数组的长度
//将每2ge相邻的子数组，进行合并排序
for(i=0;i+2*gap-1<len;i+=(2*gap)){
merge(a, i, i+gap-1, i+2*gap-1);
//若i+gap-1< len-1 ,则剩余一个子数组没有配对
//将该子数组合并到已排序的数组中
if(i+gap-1<len-1){
merge(a, i, i+gap-1, len-1);
}
}
}
/**
* 归并排序(从下往上)
*
* @param a 待排序的数组
* **/
public static void mergeSortDown2Up(int[]a){
if(a==null){
return;
}
for(int n=1;n<a.length;n*=2){
mergeGroups(a, a.length, n);
}
}
public static void main(String[] args) {
int []a={3,4,-1,44,32,9};
print("排序前: ", a);
mergeSortUp2Down(a, 0, a.length-1);
print("排序后: ", a);
}
/**
* 输出排序
*
* */
private static void print(String info,int arr[]){
System.out.println(info);
for(int a:arr){
System.out.print(a+" ");
}
System.out.println();
}
}
package com.sanjiesanxian.sort.test;
/***
*
* 不支持负数
* 基数排序
* */
public class RadixSort {
/*
* 获取数组a中最大值
*
* 参数说明：
* a -- 数组
* n -- 数组长度
*/
private static int getMax(int[] a) {
int max;
max = a[0];
for (int i = 1; i < a.length; i++)
if (a[i] > max)
max = a[i];
return max;
}
/*
* 对数组按照"某个位数"进行排序(桶排序)
*
* 参数说明：
* a -- 数组
* exp -- 指数。对数组a按照该指数进行排序。
*
* 例如，对于数组a={50, 3, 542, 745, 2014, 154, 63, 616}；
* (01) 当exp=1表示按照"个位"对数组a进行排序
* (02) 当exp=10表示按照"十位"对数组a进行排序
* (03) 当exp=100表示按照"百位"对数组a进行排序
* ...
*/
private static void countSort(int[] a, int exp) {
//int output[a.length]; // 存储"被排序数据"的临时数组
int[] output = new int[a.length]; // 存储"被排序数据"的临时数组
int[] buckets = new int[10];
// 将数据出现的次数存储在buckets[]中
for (int i = 0; i < a.length; i++)
buckets[ (a[i]/exp)%10 ]++;
// 更改buckets[i]。目的是让更改后的buckets[i]的值，是该数据在output[]中的位置。
for (int i = 1; i < 10; i++)
buckets[i] += buckets[i - 1];
// 将数据存储到临时数组output[]中
for (int i = a.length - 1; i >= 0; i--) {
output[buckets[ (a[i]/exp)%10 ] - 1] = a[i];
buckets[ (a[i]/exp)%10 ]--;
}
// 将排序好的数据赋值给a[]
for (int i = 0; i < a.length; i++)
a[i] = output[i];
output = null;
buckets = null;
}
/*
* 基数排序
*
* 参数说明：
* a -- 数组
*/
public static void radixSort(int[] a) {
int exp; // 指数。当对数组按各位进行排序时，exp=1；按十位进行排序时，exp=10；...
int max = getMax(a); // 数组a中的最大值
// 从个位开始，对数组a按"指数"进行排序
for (exp = 1; max/exp > 0; exp *= 10)
countSort(a, exp);
}
public static void print(String info,int a[]){
System.out.print(info);
for(int aa:a){
System.out.print(aa+" ");
}
System.out.println();
}
public static void main(String[] args) {
//不支持负数排序
int a[]={1,5,2,88,9};
print("排序前: ", a);
radixSort(a);
print("排序后: ", a);
}
}
声明：ITeye文章版权属于作者，受法律保护。没有作者书面许可不得转载。
推荐链接
|
||||||||||||||||||||||||||||||
| 返回顶楼 | |||||||||||||||||||||||||||||||
|
发表时间：2014-07-14
mark
|
||||||||||||||||||||||||||||||
| 返回顶楼 | |||||||||||||||||||||||||||||||
