Java實現各種排序匯總
選擇排序、快速排序、希爾排序、堆排序不是穩定的排序算法，
冒泡排序、插入排序、歸并排序和基數排序是穩定的排序算法。
</h4>
那什么是穩定的排序算法呢？
就是在排序的過程中，相等的兩個數并不會在排列后中為位置發生次序發生顛倒
再看一下各排列算法的時間效率分析匯總：
|
排序法 |
平均時間 |
最差情形 |
穩定度 |
額外空間 |
備注 |
|
冒泡 |
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] + " ");
}
}
} 本文由用戶 jopen 自行上傳分享，僅供網友學習交流。所有權歸原作者，若您的權利被侵害，請聯系管理員。
轉載本站原創文章，請注明出處，并保留原始鏈接、圖片水印。
本站是一個以用戶分享為主的開源技術平臺，歡迎各類分享！