排序
-
- 排序對比
-
-
- 數量級 1000，看不出差别
- 數量級 1W，bubble、select、insert 的劣勢已經顯現，quick 、merge 依舊優秀
- 數量級 10W，bubble、select已經跑不動了，insert的劣勢已經顯現，quick 、merge 依舊優秀
- 數量級100W，insert已經跑不動了，quick 、merge 依舊優秀，quick 對比merge，略勝一籌
- 數量級 1000W，quick 、merge 依舊優秀，quick 對比merge，略勝一籌
- 數量級 1億，quick 、merge 依舊優秀，quick 對比merge，優秀很多
冒泡排序
private static void bubbleSort(int[] nums) {
int m;
for (int i = 0; i < nums.length; i++) {
/* 前後兩個值，依次對比，調換位置 */
for (int j = 0; j < nums.length - 1; j++) {
if (nums[j] > nums[j + 1]) {
m = nums[j];
nums[j] = nums[j + 1];
nums[j + 1] = m;
}
}
}
}
選擇排序
private static void selectSort(int[] nums) {
for (int i = 0; i < nums.length - 1; i++) {
int min = i;
/* 周遊找出最小值 */
for (int j = i + 1; j < nums.length; j++) {
if (nums[j] < nums[min]) {
min = j;
}
}
/* 目前值與最小值兌換 */
if (i != min) {
int temp = nums[min];
nums[min] = nums[i];
nums[i] = temp;
}
}
}
插入排序
private static void insertSort(int[] nums) {
for (int i = 1; i < nums.length; i++) {
int j = i;
int current = nums[j];
/* 目前值（current）依次與前面的值（nums[j - 1]）對比，
如果小于，則前面的值後移一位（nums[j] = nums[j - 1]） */
while (j > 0 && current < nums[j - 1]) {
nums[j] = nums[j - 1];
j--;
}
/* 目前值（current）對比到了第一位 或者 遇到比自己小的值，則在位置j處 插入*/
nums[j] = current;
}
}
快速排序
private static void quickSort(int[] nums) {
quickSortNext(nums, 0, nums.length - 1);
}
private static void quickSortNext(int[] nums, int start, int end) {
if (start >= end) {
return;
}
int p = nums[start]; // 将第一個數（nums[start]）作為對比數
int left = start;
int right = end;
while (left <= right) {
while (left <= right && nums[left] < p) { // 從左往右，尋找比 p 大的數（nums[left]）
left++;
}
while (left <= right && nums[right] > p) { // 從右往左，尋找比 p 小的數（nums[right]）
right--;
}
if (left <= right) { // 将 nums[left] 、 nums[right] 交換
int temp = nums[right];
nums[right] = nums[left];
nums[left] = temp;
left++;
right--;
}
}
/* 一次循環之後，
start 到 right之間是比 p 小的值，
left 到 end 之間 是比 p 大的值*/
quickSortNext(nums, start, right); // 遞歸處理左半邊資料
quickSortNext(nums, left, end); // 遞歸處理右半邊資料
}
歸并排序
private static void mergeSort(int[] nums) {
int[] sort = new int[nums.length]; // 需要一個數組 記錄資料
mergeSortNext(nums, 0, nums.length - 1, sort);
}
private static void mergeSortNext(int[] nums, int start, int end, int[] sort) {
if (start >= end) {
return;
}
/* 通過遞歸，拆分成最小數組 */
int mid = (start + end) / 2;
mergeSortNext(nums, start, mid, sort); // 左半部分
mergeSortNext(nums, mid + 1, end, sort); // 右半部分
merge(nums, start, mid, end, sort); // 左、右 部分進行排序
}
private static void merge(int[] nums, int start, int mid, int end, int[] sort) {
int left = start;
int right = mid + 1;
int index = start;
/* 設定左右兩個指針（left、right）,
left 負責左半部分， right 負責右半部分
nums[left]、nums[right] 依次對比 */
while (left <= mid && right <= end) {
if (nums[left] < nums[right]) { // 将小的值 放入sort數組中，指針後移一位
sort[index++] = nums[left++];
} else {
sort[index++] = nums[right++];
}
}
while (left <= mid) { // 考慮 right 走完，但 left 沒有走完的情況
sort[index++] = nums[left++];
}
while (right <= end) { // 考慮 left 走完，但 right 沒有走完的情況
sort[index++] = nums[right++];
}
for (int i = start; i <= end; i++) { // 将sort的值 寫入 原數組
nums[i] = sort[i];
}
}
排序對比
public static void main(String[] args) {
int[] nums = new int[1000];
/*冒泡排序*/
for (int i = 0; i < nums.length; i++) {
nums[i] = (int) (Math.random() * 10000);
}
long bubbleSortStart = System.currentTimeMillis();
bubbleSort(nums);
System.out.println("bubble is done , time = " + (System.currentTimeMillis() - bubbleSortStart));
/*選擇排序*/
for (int i = 0; i < nums.length; i++) {
nums[i] = (int) (Math.random() * 10000);
}
long selectSortStart = System.currentTimeMillis();
selectSort(nums);
System.out.println("select is done , time = " + (System.currentTimeMillis() - selectSortStart));
/*插入排序*/
for (int i = 0; i < nums.length; i++) {
nums[i] = (int) (Math.random() * 10000);
}
long insertSortStart = System.currentTimeMillis();
insertSort(nums);
System.out.println("insert is done , time = " + (System.currentTimeMillis() - insertSortStart));
/*快速排序*/
for (int i = 0; i < nums.length; i++) {
nums[i] = (int) (Math.random() * 10000);
}
long quickSortStart = System.currentTimeMillis();
quickSort(nums);
System.out.println("quick is done , time = " + (System.currentTimeMillis() - quickSortStart));
/*歸并排序*/
for (int i = 0; i < nums.length; i++) {
nums[i] = (int) (Math.random() * 10000);
}
long mergeSortStart = System.currentTimeMillis();
mergeSort(nums);
System.out.println("merge is done , time = " + (System.currentTimeMillis() - mergeSortStart));
數量級 1000，看不出差别
bubble is done , time = 4
select is done , time = 2
insert is done , time = 2
quick is done , time = 0
merge is done , time = 0
數量級 1W，bubble、select、insert 的劣勢已經顯現，quick 、merge 依舊優秀
bubble is done , time = 176
select is done , time = 41
insert is done , time = 11
quick is done , time = 2
merge is done , time = 2
數量級 10W，bubble、select已經跑不動了，insert的劣勢已經顯現，quick 、merge 依舊優秀
bubble is done , time = 18155
select is done , time = 3705
insert is done , time = 690
quick is done , time = 14
merge is done , time = 11
數量級100W，insert已經跑不動了，quick 、merge 依舊優秀，quick 對比merge，略勝一籌
insert is done , time = 78902
quick is done , time = 70
merge is done , time = 102
數量級 1000W，quick 、merge 依舊優秀，quick 對比merge，略勝一籌
quick is done , time = 592
merge is done , time = 994
數量級 1億，quick 、merge 依舊優秀，quick 對比merge，優秀很多
quick is done , time = 6712
merge is done , time = 10431
![Java String.format方法的簡單使用[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)