前面一篇文章已经讲到了三个比较简单的排序算法,现在准备说一下比较高级一点的两个算法,他们在数据量比较大的时候的效果还是很明显的,我这里给出java的实现代码。
1.快速排序
过程:将待排序的第一个数作为标志temp,然后开始比较,i指向第一个数,j指向最后一个数,最开始j指向的数和temp比较,如果j比较大,j往左移动,否则i和j的数字交换,并且i开始想右边移动,知道i=j,完成一趟。一趟执行完了之后这个数就在正确的位置上面,即它不小于它左边的数,同时不大于它右边的数。
同样有一个Test类获取比较的数组。
public class Test {
//通过scan一个一个读入数据,获取输入的数组
public List Input() {
List list = new ArrayList<>();
Scanner scanner = new Scanner(System.in);
int length = 0;//数组长度
System.out.print("输入数组长度:");
length = scanner.nextInt();
System.out.print("输入排序数组:");
int count = 0;
while (length != count) {
list.add(scanner.nextInt());
count++;
}
System.out.print("输入的数组为:");
for (int j = 0; j < list.size(); j++) {
System.out.print(list.get(j) + " ");
}
return list;
}
public List getRandomInput() {
List list = new ArrayList<>();
System.out.print("输入随机数个数:");
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
System.out.print("sort before:");
boolean flag;
int a;
for (int i = 0; i < n; i++) {
flag = true;
//while循环是为了保证随机到的数组没有重复的,不然有时候如果范围比较小的下,重复比较高,这个并不影响,大家可以自行修改
while (flag) {
a = new Random().nextInt(100);
if (i == 0) {
list.add(a);
System.out.print(a + " ");
flag = false;
} else {
for (int j = 0; j < list.size(); j++) {
//判断list中是否存在a,如果不存在 就加入到list中
if ((int) list.get(j) == a) {
flag =true;
break;
}
flag = false;
}
if(!flag){
list.add(a);
System.out.print(a + " ");
}
}
}
}
System.out.print("\n");
return list;
}
}
快速排序java代码实现:
public class QuickSort {
public static void main(String[] args) {
//获取输入需要排序的数组
Test test = new Test();
//List list = test.Input();
List list = test.getRandomInput();
int low = 0;
int high = list.size() - 1;
//递归排序
long time = System.currentTimeMillis();
QuickSort quickSort = new QuickSort();
quickSort.Sort(list, low, high);
}
public void Sort(List list, int low, int high) {
int temp = (int) list.get(low);
int l = low;
int h = high;
int k;
if (l < h) {
while (l < h) {
//从右往左,查看有没有数值比temp小,如果有小的,就停止右移,继续换左移
while (l < h && (int) list.get(h) >= temp) h--;
//找到了 比temp小的值,就交换位置,同时temp的值不变
k = (int) list.get(h);
list.set(h, list.get(l));
list.set(l, k);
//从左往右移动,查看有没有数值比temp大,有就交换位置,停止左移,继续换右移,直到l = h
while (l < h && temp >= (int) list.get(l)) l++;
k = (int) list.get(h);
list.set(h, list.get(l));
list.set(l, k);
}
System.out.print("sort after:");
for (int i = 0; i < list.size(); i++) {
if(i == l){
System.out.print("{");
System.out.print(list.get(i));
System.out.print("} ");
}else System.out.print(list.get(i)+ " ");
}
System.out.println();
if(l>low){
Sort(list, low, l-1);
}
if(l<high){
Sort(list, l+1 , high);
}
}
}
}
每一趟排序好的我都用括号标志出来了,方便观察。
测试结果:

2.归并排序
过程:归并排序其实就是先用递归将数组分成一个一个的子数组,将子数组排序好,然后在将两个子数组排序合并在一起。
归并排序java代码实现:
public class MergeSort {
public static void main(String[] args) {
MergeSort mergeSort = new MergeSort();
Test test = new Test();
List list = test.getRandomInput();
//通过递归,局部排序
mergeSort.sort(list, 0, list.size() - 1);
System.out.print("sort after:");
for (int i = 0; i < list.size(); i++) {
System.out.print(list.get(i) + " ");
}
}
public void sort(List list, int low, int high) {
int mid = (low + high) / 2;
List list1 = new ArrayList<>();
if (low < high) {
//左边
sort(list, low, mid);
//右边
sort(list, mid + 1, high);
//合并
merge(list, low, high, list1);
}
}
public void merge(List list, int low, int high, List list1) {
int mid = (low + high) / 2;
int i = low;
int h = high;
int j = mid + 1;
int m = mid;
while (i <= m && j <= h) {
if ((int) list.get(i) < (int) list.get(j)) {
list1.add(list.get(i));
i++;
} else {
list1.add(list.get(j));
j++;
}
}
while (i <= m) {
list1.add(list.get(i));
i++;
}
while (j <= h) {
list1.add(list.get(j));
j++;
}
for (i = 0; i < list1.size(); i++)
list.set(low+i, list1.get(i));
}
}
测试结果:

以上都是自己用IDEA写的代码,亲测可行。大家可以直接拷贝运行测试,如果大家想测试效率,可以将Test类中随机的范围编程10000+,然后生成5000+的数组,然后使用
long time = System.currentTimeMillis();
//排序代码快
System.out.print(System.currentTimeMillis() - time);
这样就可以打印时间了。
如果大家有什么更好的代码实现,或者我的代码有什么问题,欢迎大家提意见