由java 复习003跳转过来的
C语言实现版见some-sort-algorithms
-
快速排序（不稳定 O(n log n)）
package vell.bibi.sort_algorithms; import vell.bibi.sort_algorithms.util.vell001; public class QuickSort { public static int partition(int[] a, int low, int high){
int cup;
cup = a[low]; // 保存关键字
while(high > low){
while(high > low && a[high] >= cup) high--; // 由high开始找，找到小于关键字的位置
a[low] = a[high];
while(high > low && a[low] <= cup) low ++; // 由low开始找，找到大于关键字的位置
a[high] = a[low];
}
a[low] = cup;
return low;
}
public static void sort(int[] a, int low, int high){
if(high <= low) return;
int mid = partition(a, low, high); // 分成两个区
sort(a, low, mid-1);
sort(a, mid+1, high);
}
public static void main(String[] args) {
int[] a = vell001.getRandomList(10, 100);
vell001.printList(a);
sort(a, 0, a.length-1);
vell001.printList(a);
}
} -
冒泡排序 （稳定 O(n2)）
package vell.bibi.sort_algorithms; import vell.bibi.sort_algorithms.util.vell001; public class BubbleSort { public static void sort(int[] a){
int i, j, cup;
boolean flag;
for(i=a.length, flag=true; flag && i>0; i--){
flag = false;
for(j=0; j<i-1; j++){
if(a[j] > a[j+1]){
cup = a[j];
a[j] = a[j+1];
a[j+1] = cup;
flag = true;
}
}
}
}
public static void main(String[] args) {
int[] a = vell001.getRandomList(10, 100);
vell001.printList(a);
sort(a);
vell001.printList(a);
} } -
希尔排序（不稳定 O(n log n)）
package vell.bibi.sort_algorithms; import vell.bibi.sort_algorithms.util.vell001; public class ShellSort {
public static void sort(int[] a){
int i, j, d, cup;
for(d=a.length/2; d>0; d=d/2){
for(i=d; i<a.length; i++){
cup = a[i];
for(j=i-d; j>=0 && a[j]>cup; j=j-d){
a[j+d] = a[j];
}
a[j+d] = cup;
}
}
}
public static void main(String[] args) {
int[] a = vell001.getRandomList(10, 100);
vell001.printList(a);
sort(a);
vell001.printList(a);
} } -
堆排序（不稳定 O(n log n)）
package vell.bibi.sort_algorithms; import vell.bibi.sort_algorithms.util.vell001; public class HeapSort { public static void heapAdjust(int[] a, int father, int length){
int child, cup;
for(child=father*2+1, cup=a[father]; child<length; father=child, child=father*2+1){
if(child+1 < length && a[child+1] > a[child])
child ++;
if(a[child] > cup){
a[father] = a[child];
a[child] = cup;
} else
break;
}
}
public static void sort(int[] a){
int cup;
for(int i=a.length/2; i>=0; i--){
heapAdjust(a, i, a.length);
}
for(int i=a.length-1; i>0; i--){
cup = a[0];
a[0] = a[i];
a[i] = cup;
heapAdjust(a, 0, i);
}
}
public static void main(String[] args) {
int[] a = vell001.getRandomList(10, 100);
vell001.printList(a);
sort(a);
vell001.printList(a);
} } -
归并排序（稳定 O(n log n) 需要O(n)额外空间）
package vell.bibi.sort_algorithms; import vell.bibi.sort_algorithms.util.vell001; public class MergeSort {
public static void merge(int[] a, int low, int mid, int high){
int i=low, j=mid, k=0;
int[] cup = new int[high-low];
while(i<mid && j<high){
if(a[i] <= a[j])
cup[k++] = a[i++];
else
cup[k++] = a[j++];
}
while(i<mid) cup[k++] = a[i++];
while(j<high) cup[k++] = a[j++];
for(k=0; k<cup.length; k++){
a[low + k] = cup[k];
}
}
public static void sort(int[] a, int low, int high){
if(high - low <= 1) return;
int mid = (high + low) / 2;
sort(a, low, mid);
sort(a, mid, high);
merge(a, low, mid, high);
} public static void main(String[] args) {
int[] a = vell001.getRandomList(10, 100);
vell001.printList(a);
sort(a, 0, a.length);
vell001.printList(a);
} } -
vell001.java (我的小工具库)
package vell.bibi.sort_algorithms.util; public class vell001 {
public static void printList(int[] a){
for(int i=0; i<a.length; i++){
System.out.print(a[i] + " ");
}
System.out.println();
}
public static int[] getRandomList(int n, int max){
int[] a = new int[n];
for(int i=0; i<n; i++){
a[i] = (int)(Math.random() * max);
}
return a;
}
}
原文地址: http://vview.ml/2014/04/13/some-sort-algorithms-java.html
written by Vell Bibi posted at VBlog