Java实现各种排序汇总

分享到:

选择排序、快速排序、希尔排序、堆排序不是稳定的排序算法,

冒泡排序、插入排序、归并排序和基数排序是稳定的排序算法。

 

那什么是稳定的排序算法呢?


就是在排序的过程中,相等的两个数并不会在排列后中为位置发生次序发生颠倒

再看一下各排列算法的时间效率分析汇总:


排序法

平均时间

最差情形

稳定度

额外空间

备注

冒泡

O(n2)

    O(n2)

稳定

O(1)

n小时较好

选择

O(n2)

O(n2)

不稳定

O(1)

n小时较好

插入

O(n2)

O(n2)

稳定

O(1)

大部分已排序时较好

基数

O(logRB)

O(logRB)

稳定

O(n)

B是真数(0-9),

R是基数(个十百)

希尔

O(nlogn)

O(ns) 1<s<2

不稳定

O(1)

s是所选分组

快速

O(nlogn)

O(n2)

不稳定

O(nlogn)

n大时较好

归并

O(nlogn)

O(nlogn)

稳定

O(1)

n大时较好

O(nlogn)

O(nlogn)

不稳定

O(1)

n大时较好




一、冒泡排序
/**
* 冒泡排序
*
* @author 陈雪桂
*
*/
public class BubbleSort
{
public static void main(String[] args)
{
BubbleSort b = new BubbleSort();
int[] a = b.init(args);
a = b.bubbleSort(a);
System.out.print("排序结果: ");
b.print(a);
}
/**
* 初始化数组
*
* @param args
* @return
*/
private int[] init(String args[])
{
int[] a = new int[args.length];
for (int i = 0; i < args.length; i++)
{
a[i] = Integer.valueOf(args[i]);
}
return a;
}
/**
* 排序核心部分
*
* @param a
* @return
*/
private int[] bubbleSort(int[] a)
{
int temp;
for (int i = 0; i < a.length; i++)
for (int j = 0; j < a.length - i - 1; j++)
{
if (a[j] > a[j + 1])
{
temp = a[j];
a[j] = a[j + 1];
a[j + 1] = temp;
}
}
return a;
}
/**
* 打印
* @param a
*/
private void print(int[] a)
{
for (int i = 0; i < a.length; i++)
{
System.out.print(a[i] + " ");
}
}
}  

二、选择排序
/**
* 选择排序
*
* @author 陈雪桂
*
*/
public class SelectionSort
{
public static void main(String[] args)
{
SelectionSort s = new SelectionSort();
int[] a = s.init(args);
a = s.selectionSort(a);
System.out.print("排序结果: ");
s.print(a);
}
/**
* 初始化数组
*
* @param args
* @return
*/
private int[] init(String args[])
{
int[] a = new int[args.length];
for (int i = 0; i < args.length; i++)
{
a[i] = Integer.valueOf(args[i]);
}
return a;
}
/**
* 选择排序核心
*
* @param a
* @return
*/
private int[] selectionSort(int[] a)
{
int min;
int temp;
for (int i = 0; i < a.length; i++)
{
min = i;
for (int j = i + 1; j < a.length; j++)
{
if (a[j] < a[min])
{
min = j;
}
}
temp = a[i];
a[i] = a[min];
a[min] = temp;
}
return a;
}
/**
* 打印
*
* @param a
*/
private void print(int[] a)
{
for (int i = 0; i < a.length; i++)
{
System.out.print(a[i] + " ");
}
}
}  

三、插入排序
/**
* 插入排序
*
* @author Administrator
*
*/
public class InsertSort
{
public static void main(String[] args)
{
InsertSort insertSort = new InsertSort();
int[] a = insertSort.init(args);
a = insertSort.insertSort(a);
System.out.print("排列顺序: ");
insertSort.print(a);
}
// 初始划排列数组
private int[] init(String[] args)
{
int[] j = new int[args.length];
for (int i = 0; i < args.length; i++)
{
j[i] = Integer.valueOf(args[i]);
}
return j;
}
// 增序排列
private int[] insertSort(int[] a)
{
int temp;
for (int i = 1; i < a.length; i++)
{
temp = a[i];
int j = i - 1;
for (; j >= 0 && a[j] > temp; j--)
{
a[j + 1] = a[j];
}
a[j + 1] = temp;
}
return a;
}
private void print(int[] a)
{
for (int i = 0; i < a.length; i++)
{
System.out.print(a[i] + " ");
}
}
}  

四、基数排序
/**
* 基数排序 平均时间复杂度:O(dn)(d即表示整形的最高位数)
* 空间复杂度:O(10n) (10表示0~9,用于存储临时的序列)
* 稳定性:稳定
*
* @author 陈雪桂
*
*/
public class RadixSort
{
/**
* 最大数的位数
*/
static int max_Pos = 2;
public static void main(String[] args)
{
RadixSort r = new RadixSort();
int[] a = r.init(args);
a = r.radixSort(a, a.length);
System.out.print("排列结果: ");
r.print(a);
}
/**
* 初始化数组
*
* @param args
* @return
*/
private int[] init(String args[])
{
int[] a = new int[args.length];
for (int i = 0; i < args.length; i++)
{
a[i] = Integer.valueOf(args[i]);
}
return a;
}
private int[] radixSort(int[] data, int dataSize)
{
List<Integer>[] bucket = new ArrayList[10];
for (int pos = 1; pos <= max_Pos; pos++)
{
for (int i = 0; i < dataSize; i++)
{
int num = getNumAtPos(data[i], pos - 1);
if (null == bucket[num])
{
bucket[num] = new ArrayList<Integer>();
}
bucket[num].add(data[i]);
}
for (int i = 0, j = 0; i < 10; i++)
{
for (int k = 0; bucket[i] != null && k < bucket[i].size(); k++)
{
data[j++] = bucket[i].get(k);
}
if (bucket[i] != null)
{
bucket[i].clear();
}
}
}
return data;
}
/**
* 获取当前位上数字
*
* @param num
* @param pos
* @return
*/
private int getNumAtPos(int num, int pos)
{
int temp = 1;
for (int i = 0; i < pos; i++)
{
temp *= 10;
}
return (num / temp) % 10;
}
private void print(int[] a)
{
for (int i = 0; i < a.length; i++)
{
System.out.print(a[i] + " ");
}
}
}  

五、希尔排序
/**
* 希尔排序
*
* @author 陈雪桂
*
*/
public class ShellSort
{
public static void main(String[] args)
{
ShellSort s = new ShellSort();
int[] a = s.init(args);
a = s.shellSort(a);
System.out.print("排列顺序 : ");
s.print(a);
}
/**
* 初始化数组
*
* @param args
* @return
*/
private int[] init(String args[])
{
int[] a = new int[args.length];
for (int i = 0; i < args.length; i++)
{
a[i] = Integer.valueOf(args[i]);
}
return a;
}
/**
* 希尔排序核心1
*
* @param args
* @return
*/
private int[] shellSort(int[] a)
{
for (int step = a.length / 2; step >= 1; step = step/2)
{
a = shellInsert(a, step);
}
return a;
}
/**
* 增序排列
*
* @param a
* @param step
* @return
*/
private int[] shellInsert(int[] a, int step)
{
int min = 0;
for (int i = step; i < a.length; i++)
{
if (a[i] < a[i - step])
{
min = a[i];
int j;
for (j = i - step; j >= 0 && a[j] > min; j -= step)
{
a[j + step] = a[j];
}
a[j + step] = min;
}
}
return a;
}
/**
* 打印
*
* @param a
*/
private void print(int[] a)
{
for (int i = 0; i < a.length; i++)
{
System.out.print(a[i] + " ");
}
}
}  

六、快速排序
/**
* 快速排序
*
* @author 陈雪桂
*
*/
public class QuickSort
{
static int count = 0;
public static void main(String[] args)
{
QuickSort q = new QuickSort();
int[] list = new int[12];
for (int i = 0; i < args.length; i++)
{
list[i] = Integer.valueOf(args[i]);
}
q.quickSort(list, 0, list.length - 1);
System.out.print("排序顺序: ");
for (int i = 0; i < list.length; i++)
{
System.out.print(list[i] + " ");
}
System.out.println("\n执行次数:" +count );
}
public void quickSort(int[] n, int from, int to)
{
if (from <= to)
{
int midSort = partition(n, from, to);
quickSort(n, from, midSort - 1);
quickSort(n, midSort + 1, to);
}
return;
}
public int partition(int[] n, int from, int to)
{
int i = from + 1;
int j = to;
int p = n[from];
while (i < j)
{
while (n[i] < p)
i++;
while (n[j] > p)
j--;
swap(n, i, j);
count ++;
}
// 判断是否有必要撤销最后一次交换,必要则不用在循环中加入边界检查条件
if(i != from+1 || j !=to)swap(n, i, j);
swap(n,from,j);
return j;
}
public void swap(int[] n, int i, int j)
{
int temp = n[i];
n[i] = n[j];
n[j] = temp;
}
}  

七、合并排序
/**
* 合并排序
* @author 陈雪桂
*
*/
public class MergeSort
{
public static void main(String[] args)
{
int[] list = new int[12];
for (int i = 0; i < args.length; i++)
{
list[i] = Integer.valueOf(args[i]);
}
list = new MergeSort().mergeSort(list, 0, list.length-1);
System.out.print("排列顺序:  ");
for (int i = 0; i < list.length; i++)
{
System.out.print(list[i] + " ");
}
}
public int[] mergeSort(int[] list, int from, int to)
{
if (from != to)
{
int mid = (from + to) / 2;
mergeSort(list, from, mid);
mergeSort(list, mid + 1, to);
return merge(list, from, to);
}
return list;
}
public int[] merge(int[] list, int from, int to)
{
int i = from;
int mid = (from + to) / 2;
int j = mid + 1;
int[] a = new int[to - from + 1];
int count = 0;
while (i <= mid && j <= to)
{
if (list[i] < list[j])
{
a[count++] = list[i++];
}
else
{
a[count++] = list[j++];
}
}
// 把剩余部分都加进去
while (i <= mid)
{
a[count++] = list[i++];
}
while (j <= to)
{
a[count++] = list[j++];
}
for(int k=from; k<= to; k++)
{
list[k] = a[k-from];
}
return list;
}
}  


八、堆排序
/**
* 堆排序包括两个步骤 (1)初始堆(堆的定义:(1)堆是一个完全二叉树(2)根结点的值或者大于左右子树的值或者小于左右子树的值(3)左右子树也是一个堆)
* (2)调整堆(当初始小顶堆之后,堆顶元素是最小的元素,取出最小的元素与最后一个元素相交换,再把剩下n-1个元素调整成堆,依次调整直到1为止)
* 非终端节点调整 初始堆时从n/2向上调整成堆 把第一个元素与最后一个元素交换之后从第1个元素开始调整成新堆
*
*
* 时间复杂度为O(nlogn) 辅助空间为O(1)
*
* @author 陈雪桂
*
*/
public class HeapSort
{
public static void main(String[] args)
{
HeapSort h = new HeapSort();
int[] a = init(args);
heapSort(a);
System.out.print("排列顺序: ");
print(a);
}
/**
* 初始化数组
*
* @param args
* @return
*/
private static int[] init(String[] args)
{
int[] a = new int[args.length];
for (int i = 0; i < args.length; i++)
{
a[i] = Integer.valueOf(args[i]);
}
return a;
}
/**
* 堆排序核心部分
*
* @param num
*/
private static void heapSort(int[] num)
{
int temp;
// 初始建堆从n/2开始向根调整
for (int i = num.length / 2 - 1; i >= 0; i--)
{
adjustHeap(num, i, num.length);// 初始堆过程
}
for (int i = num.length - 1; i > 0; i--)
{
// 将堆顶元素与i元素交换
temp = num[i];
num[i] = num[0];
num[0] = temp;
// 从num[1]到num[i-1]调整成新堆
adjustHeap(num, 0, i - 1);
}
}
/**
* 调整堆
*
* @param num
* @param s
*
调整开始父节点
* @param t
*
调整结尾的界限
*/
private static void adjustHeap(int[] num, int s, int t)
{
int x = num[s];
// 从最下父节点 与子节点比较,一直向上进行调整
for (int j = 2 * s + 1; j <= t; j = 2 * j + 1)
{
// 找出较大者把较大者给num[i]
if (j < t && num[j] < num[j + 1])
{
j = j + 1;
}
if (j < t && x < num[j])
{
num[s] = num[j];
s = j;
}
}
num[s] = x;
}
/**
* 打印
*
* @param a
*/
private static void print(int[] a)
{
for (int i = 0; i < a.length; i++)
{
System.out.print(a[i] + " ");
}
}
}  
昵    称:
验证码:

相关文档: