冒泡排序
冒泡排序(Bubble Sort),是一种计算机科学领域的较简单的排序算法。 它重复地走访过要排序的元素列,依次比较两个相邻的元素,如果顺序(如从大到小、首字母从Z到A)错误就把他们交换过来。走访元素的工作是重复地进行直到没有相邻元素需要交换,也就是说该元素列已经排序完成。 这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端(升序或降序排列),就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样,故名“冒泡排序”。
选择排序
选择排序(Selection sort)是一种简单直观的排序算法。它的工作原理是每一次从待排序的数据元素中选出最小(或最大)的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。 选择排序是不稳定的排序方法(比如序列[5， 5， 3]第一次就将第一个[5]与[3]交换，导致第一个5挪动到第二个5后面)。
快速排序
快速排序算法通过多次比较和交换来实现排序，其排序流程如下：
(1)首先设定一个分界值，通过该分界值将数组分成左右两部分。
(2)将大于或等于分界值的数据集中到数组右边，小于分界值的数据集中到数组的左边。此时，左边部分中各元素都小于分界值，而右边部分中各元素都大于或等于分界值。
(3)然后，左边和右边的数据可以独立排序。对于左侧的数组数据，又可以取一个分界值，将该部分数据分成左右两部分，同样在左边放置较小值，右边放置较大值。右侧的数组数据也可以做类似处理。
(4)重复上述过程，可以看出，这是一个递归定义。通过递归将左侧部分排好序后，再递归排好右侧部分的顺序。当左、右两个部分各数据排序完成后，整个数组的排序也就完成了。
package com.caozz.demo.config;
import java.util.Random;
/**
* @Author: caozz
* @Date: 2023/8/9 17:21
* @Version: v1.0
**/
public class Test {
public static void main(String[] args) {
// int[] quickArr = {6, 1, 2, 7, 9, 3, 4, 5, 10, 8};
int[] quickArr = new int[1000000];
int[] bubbleArr = new int[1000000];
int[] selectionArr = new int[1000000];
Random random = new Random();
for (int i = 0; i < quickArr.length; i++) {
int ele = random.nextInt();
quickArr[i] = ele;
bubbleArr[i] = ele;
selectionArr[i] = ele;
}
long t1 = System.currentTimeMillis();
quickSort(quickArr,0,quickArr.length-1);
long t2 = System.currentTimeMillis();
bubbleSort(bubbleArr);
long t3 = System.currentTimeMillis();
selectionSort(selectionArr);
long t4 = System.currentTimeMillis();
System.out.println("快速排序花费时间：" + (t2-t1));
System.out.println("冒泡排序花费时间：" + (t3-t2));
System.out.println("选择排序花费时间：" + (t4-t3));
}
public static void quickSort(int[] arr, int i, int j){
//定义两个变量，以及要查找的范围
int start = i;
int end = j;
//递归出口
if (start > end) {
return;
}
int baseNumber = arr[i]; //记录基准数
//利用循环查找要交换的数字
while (start != end) {
//利用end,从后往前找，找到比基准数小的数字
while (true) {
if (end <= start || arr[end] < baseNumber) {break;}
end--;
}
//利用start，从前往后找，找到比基准数大的数字
while (true) {
if (end <= start || arr[start] > baseNumber) {break;}
start++;
}
//交换元素
int temp = arr[start];
arr[start] = arr[end];
arr[end] = temp;
}
//当start与end指向了同一个元素的时候，那么上面的循环就会结束
//表示已经找到了基准数在数组中应存入的位置
//基准数归位
//就是拿着这个范围的第一个数字，跟start或ens的数字进行交换
int tmp = arr[i];
arr[i] = arr[start];
arr[start] = tmp;
//确定刚才基准数左边的范围重复刚才的过程
quickSort(arr,i,start-1);
//确定刚才基准数左边的范围重复刚才的过程
quickSort(arr,start+1,j);
}
public static void bubbleSort(int[] arr) {
//需要几轮，因为当将前面元素都冒泡排序正确，最后一个一定正确，故减一
for (int i=0;i < arr.length-1; i++) {
//减一是因为倒数第二个与最后一个已经是最后一次，减i是因为已经冒泡的不用再次比较
for (int j = 0; j < arr.length -1 - i; j++) {
//顺序不对则交换
if (arr[i] > arr[i+1]) {
int temp = arr[i];
arr[i] = arr[i+1];
arr[i+1] = temp;
}
}
}
}
public static void selectionSort(int[] arr) {
//需要几轮
for (int i = 0; i < arr.length -1; i++) {
//i+1是因为不用和自身比较
for (int j=i+1; j< arr.length; j++) {
//顺序不对则交换
if (arr[i] > arr[j]) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
}
}
}
随机生成十万数据的结果
随机生成十万数据的结果
快速排序花费时间：28
冒泡排序花费时间：5180
选择排序花费时间：12431
随机生成一百万数据的结果
快速排序花费时间：125
冒泡排序花费时间：523672
选择排序花费时间：1295557
欢迎大家留言，以便于后面的人更快解决问题！另外亦欢迎大家可以关注我的微信公众号，方便利用零碎时间互相交流。共勉！
