# 【笔记】排序算法整理

2019/01/28 21:02

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
* @version 2013年10月22日
* @author yuanqy
*/
public class Sort {

public static void main(String[] args) {
testSuc(); // 成功测试
testRun(10000, 100000, 10000); // 性能测试
}

public static void testRun(int start, int end, int step) {
for (int i = start; i <= end; i = step + i) {
final int[] data = (getRundom(i, Integer.MAX_VALUE));
System.out.print("数据量：" + data.length + "\t");
BubbleSort(Arrays.copyOf(data, data.length));
SelectSort(Arrays.copyOf(data, data.length));
InsertSort(Arrays.copyOf(data, data.length));
InsertSplitSort(Arrays.copyOf(data, data.length));
MergeSort(Arrays.copyOf(data, data.length));
InsertShellSort(Arrays.copyOf(data, data.length));
HeapSort(Arrays.copyOf(data, data.length));
QuickSort(Arrays.copyOf(data, data.length));
System.out.println("");
}
}

public static void testSuc() {
final int[] data = (getRundom(15, Integer.MAX_VALUE));
System.out.println(Arrays.toString(data));
System.out.println("插入排序:");
System.out.println(Arrays.toString(InsertSort(Arrays.copyOf(data, data.length))));
System.out.println(Arrays.toString(InsertSplitSort(Arrays.copyOf(data, data.length))));
System.out.println(Arrays.toString(InsertShellSort(Arrays.copyOf(data, data.length))));
System.out.println("选择排序:");
System.out.println(Arrays.toString(SelectSort(Arrays.copyOf(data, data.length))));
System.out.println(Arrays.toString(HeapSort(Arrays.copyOf(data, data.length))));
System.out.println("交换排序:");
System.out.println(Arrays.toString(BubbleSort(Arrays.copyOf(data, data.length))));
System.out.println(Arrays.toString(QuickSort(Arrays.copyOf(data, data.length))));
System.out.println(Arrays.toString(MergeSort(Arrays.copyOf(data, data.length))));
}
// ======================================

public static int[] InsertSort(int[] sz) {
int[] data = sz;
long beginTime = System.currentTimeMillis();
for (int i = 1; i < data.length; i++) {
for (int j = i; (j > 0) && (data[j] < data[j - 1]); j--) {
swap(data, j, j - 1);
}
}
long endTime = System.currentTimeMillis();
System.out.print("直接插入[" + (endTime - beginTime) + "]\t");
return data;
}

public static int[] InsertSplitSort(int[] sz) {
int[] data = sz;
long beginTime = System.currentTimeMillis();
for (int i = 1; i < data.length; i++) {
int tmp = data[i];
int min = 0;
int big = i - 1;
while (big >= min) {
int mid = (min + big) / 2;
if (tmp > data[mid]) {
min = mid + 1;
} else {
big = mid - 1;
}
}
for (int j = i; j > min; j--) {
data[j] = data[j - 1];
}
data[big + 1] = tmp;
}
long endTime = System.currentTimeMillis();
System.out.print("折半插入[" + (endTime - beginTime) + "]\t");
return data;
}

public static int[] InsertShellSort(int[] sz) {
int[] data = sz;
long beginTime = System.currentTimeMillis();
int span = data.length / 7;
if (span == 0)
span = 1;
while (span >= 1) {
for (int i = 0; i < span; i++) {
for (int j = i; j < data.length; j = j + span) {
// 组内直接插入排序
int p = j - span;
int temp = data[j];
while (p >= 0 && data[p] > temp) {
data[p + span] = data[p];
p -= span;
}
data[p + span] = temp;
}
}
span = span / 2;
}
long endTime = System.currentTimeMillis();
System.out.print("希尔插入[" + (endTime - beginTime) + "]\t");
return data;
}

public static int[] BubbleSort(int[] sz) {
int[] data = sz;
long beginTime = System.currentTimeMillis();
for (int i = 0; i < data.length; i++) {
for (int j = i + 1; j <= data.length - 1; j++) {
if (data[i] > data[j]) {
swap(data, i, j);
}
}
}
long endTime = System.currentTimeMillis();
System.out.print("冒泡排序[" + (endTime - beginTime) + "]\t");
return data;
}

public static int[] SelectSort(int[] sz) {
int[] data = sz;
long beginTime = System.currentTimeMillis();
for (int i = 0; i < data.length; i++) {
int beginIndex = i;
for (int j = data.length - 1; j > i; j--) {
if (data[j] < data[beginIndex]) {
beginIndex = j;
}
}
swap(data, i, beginIndex);
}
long endTime = System.currentTimeMillis();
System.out.print("选择排序[" + (endTime - beginTime) + "]\t");
return data;
}

public static int[] HeapSort(int[] sz) {
int[] data = sz;
long beginTime = System.currentTimeMillis();
int n = data.length;
for (int i = n / 2; i >= 0; i--) {
keepHeap(data, n, i);
}
while (n > 0) {
swap(data, 0, n - 1);
keepHeap(data, --n, 0);
}
long endTime = System.currentTimeMillis();
System.out.print("堆排序[" + (endTime - beginTime) + "]\t");
return data;
}

private static void keepHeap(int[] a, int n, int i) {
int x = a[i];
int j = 2 * i + 1;
while (j <= n - 1) {
if (j < n - 1 && a[j] < a[j + 1])
++j;
if (a[j] > x) {
a[i] = a[j];
i = j;
j = 2 * i;
} else {
break;
}
}
a[i] = x;
}

public static int[] QuickSort(int[] sz) {
int start = 0, end = sz.length - 1;
long beginTime = System.currentTimeMillis();
reQuickSort(sz, start, end);
long endTime = System.currentTimeMillis();
System.out.print("快速排序[" + (endTime - beginTime) + "]\t");
return sz;
}

public static int[] reQuickSort(int[] data, int start, int end) {
int i = start + 1, j = end;
int key = data[start];
/*
* 从i++和j--两个方向搜索不满足条件的值并交换 条件为：i++方向小于key，j--方向大于key
*/
while (true) {
while (data[j] > (key))
j--;
while (data[i] < (key) && i < j)
i++;
if (i >= j)
break;
swap(data, i, j);
if (data[i] == key) {
j--;
} else {
i++;
}
}
/* 关键数据放到‘中间’ */
swap(data, start, j);
if (start < i - 1) {
reQuickSort(data, start, i - 1);
}
if (j + 1 < end) {
reQuickSort(data, j + 1, end);
}
return data;
}

public static int[] MergeSort(int[] sz) {
int[] data = sz;
long beginTime = System.currentTimeMillis();
int[] result = merge_sort(data, 0, data.length - 1);
for (int i = 0; i < result.length; i++) {
data[i] = result[i];
}
long endTime = System.currentTimeMillis();
System.out.print("归并排序[" + (endTime - beginTime) + "]\t");
return data;
}

private static int[] merge_sort(int[] array, int start, int end) {
int[] result = new int[end - start + 1];
if (start < end) {
int mid = (start + end) / 2;
int[] left = merge_sort(array, start, mid);
int[] right = merge_sort(array, mid + 1, end);
result = merge(left, right);
} else if (start == end) {
result[0] = array[start];
return result;
}
return result;
}

private static int[] merge(int[] left, int[] right) {
int[] result = new int[left.length + right.length];
int i = 0;
int j = 0;
int k = 0;
while (i < left.length && j < right.length) {
if (left[i] < right[j]) {
result[k++] = left[i++];
} else {
result[k++] = right[j++];
}
}
while (i < left.length) {
result[k++] = left[i++];
}
while (j < right.length) {
result[k++] = right[j++];
}
return result;
}

public static int[] radixSort(int[] sz) {
int[] data = sz;
long beginTime = System.currentTimeMillis();
// 首先确定排序的趟数;
int max = data[0];
for (int i = 1; i < data.length; i++) {
if (data[i] > max) {
max = data[i];
}
}
int time = 0;
// 判断位数;
while (max > 0) {
max /= 10;
time++;
}
// 建立10个队列;
List<ArrayList> queue = new ArrayList<ArrayList>();
for (int i = 0; i < 10; i++) {
ArrayList<Integer> queue1 = new ArrayList<Integer>();
}
// 进行time次分配和收集;
for (int i = 0; i < time; i++) {
// 分配数组元素;
for (int j = 0; j < data.length; j++) {
// 得到数字的第time+1位数;
int x = data[j] % (int) Math.pow(10, i + 1) / (int) Math.pow(10, i);
ArrayList<Integer> queue2 = queue.get(x);
queue.set(x, queue2);
}
int count = 0;// 元素计数器;
// 收集队列元素;
for (int k = 0; k < 10; k++) {
while (queue.get(k).size() > 0) {
ArrayList<Integer> queue3 = queue.get(k);
data[count] = queue3.get(0);
queue3.remove(0);
count++;
}
}
}
long endTime = System.currentTimeMillis();
System.out.print("基数排序[" + (endTime - beginTime) + "]\t");
return data;
}

// ====== 调换位置 ===============================
private static void swap(int[] data, int x, int y) {
int temp = data[x];
data[x] = data[y];
data[y] = temp;

}

// ====== 获取随机数 ===============================
private static int[] getRundom(long num, int maxVal) {
List<Integer> list = new ArrayList<Integer>();
int n = 0, m = maxVal;
for (long i = 0; i < num; i++) {
list.add((int) (Math.random() * (n - m) + m));
}
return list.stream().mapToInt(Integer::valueOf).toArray();
}
// 1.稳定性比较
//
// 插入排序、冒泡排序、二叉树/二路归并排序及其他线形排序是稳定的
//
// 选择排序、希尔排序、快速排序、堆排序是不稳定的
//
// 2.时间复杂性比较
//
// 插入排序、冒泡排序、选择排序的时间复杂性为O(n2)
//
// 其它非线形排序的时间复杂性为O(nlog2n)
//
// 线形排序的时间复杂性为O(n);
//
// 3.辅助空间的比较
//
// 线形排序、二路归并排序的辅助空间为O(n),其它排序的辅助空间为O(1);
//
// 4.其它比较
//
// 插入、冒泡排序的速度较慢，但参加排序的序列局部或整体有序时，这种排序能达到较快的速度。
//
// 反而在这种情况下，快速排序反而慢了。
//
// 当n较小时，对稳定性不作要求时宜用选择排序，对稳定性有要求时宜用插入或冒泡排序。
//
// 若待排序的记录的关键字在一个明显有限范围内时,且空间允许是用桶排序。
//
// 当n较大时，关键字元素比较随机，对稳定性没要求宜用快速排序。
//
// 当n较大时，关键字元素可能出现本身是有序的，对稳定性有要求时，空间允许的情况下。
//
// 宜用归并排序。
//
// 当n较大时，关键字元素可能出现本身是有序的，对稳定性没有要求时宜用堆排序。
//
// *************************************************************************************

}


0
0 收藏

0 评论
0 收藏
0