排序算法代碼實現-Java
前言
為了準備面試，從2月開始將排序算法認認真真得刷了一遍，通過看書看視頻，實踐打代碼，還有一部分的leetcode題，自己感覺也有點進步，將筆記記錄總結髮出來。
冒泡排序
- 該排序就是一種像泡泡浮到水面以後，將其挑選，這種浮出來的前提是就是或者是小的/大的先露頭，將/小的大的檢索出來。（根據從大到小或者反過來）
package src.datastructure;
import java.util.Arrays;
/**
* @Author: yhy
* @Time: 23:49
*/
//時間複雜度O(n^2)
public class DubbleSort {
public static void main(String[] args) {
int[] abc = {1,9,-2,40,33};
int temp = 0;
boolean flag = false;
//第一輪for，n個數都要參與比較。
for (int i = 0; i <abc.length-1 ; i++) {
//第1個和其他的數進行比較。。再到第二個數與其他的
for (int j = 0; j < abc.length-1 ; j++) {
//這裡是升序排序
if (abc[j] > abc[j+1]) {
flag = true;
temp = abc[j];
abc[j] = abc[j+1];
abc[j+1] = temp;
}
}
//這裡優化了一些，減少了比較的次數，若排好序了，就直接跳出循環，輸出結果
if (!flag) {
break;
}else {
flag = false;
}
}
System.out.println(Arrays.toString(abc));
}
}
選擇排序
- 先找個值假設作為最小值，進行該值以後的數與該值比較，小的就放在前面
package src.datastructure;
import java.util.Arrays;
/**
* @Author: yhy
* @Time: 15:30
* 選擇排序
*/
public class SelectSort {
public static void main(String[] args) {
int[] abc = {1,9,-2,40,33};
// 選擇排序：選擇一開始為最小的，然後每一次開始排序
// 也有最小值還有最小值的索引
for (int i = 0; i < abc.length; i++) {
int min = abc[i];
int minIndex = i;
for (int j = i+1; j < abc.length; j++) {
if (min > abc[j]) {
min = abc[j];
minIndex = j;
abc[j] = abc[i];
}
// 關鍵判斷;要將原來的索引與min比較，若發生了交換，就將相對小的數放在前面去
if (minIndex != i) {
abc[i] = min;
}
}
}
System.out.println(Arrays.toString(abc));
}
}
插入排序
- 插入意思就是從無序區找值插到有序區去，所以取第一個值為有序區，等到有序區長度為n（數組長度）時候就成功排序。
package src.datastructure;
import java.util.Arrays;
/**
* @Author: yhy
* @Time: 15:30
*/
public class InsertSort {
public static void main(String[] args) {
int[] abc = {1,9,-2,40,33};
// 插入排序,分為有序區,和無序區
// 和選擇排序有那麼一點相似,
// 這裡是將一部分定義為有,然後比較再選擇插入的位置等
for (int i = 1; i < abc.length ; i++) {
int insertIndex = i -1;
int insertValue = abc[i];
// 這裡的數組下標是可以等於0
while (insertIndex >= 0 && insertValue < abc[insertIndex]){
// 將大的值往後移,直到找到合適的插入位置
abc[insertIndex+1] = abc[insertIndex];
insertIndex--;
}
// 退出循環後,就說明插入的位置找到了 加入判斷,如果沒有進去while的話,就不用賦值,插入位置不變
if (insertIndex + 1 != i) {
abc[insertIndex+1] = insertValue;
}
}
System.out.println(Arrays.toString(abc));
}
}
快速排序
- 一種雙指針移動的排序，找個基準值
package src.datastructure;
import java.util.Arrays;
/**
* @Author: yhy
* @Time: 12:05
* 採用指針交換來做
*/
public class QuickSort2 {
public static void quickSort(int[] arr, int startIndex, int endIndex) {
// 遞歸結束:startIndex 大於等於endIndex的時候
if (startIndex >= endIndex) {
return;
}
// 得到基準元素位置
int pivotIndex = partition(arr, startIndex, endIndex);
// 使用分治法遞歸數列的兩部分
quickSort(arr, startIndex, pivotIndex - 1);
quickSort(arr, pivotIndex + 1, endIndex);
}
public static int partition(int[] arr, int startIndex, int endIndex) {
// 這裡的交換次數更少了
int pivot = arr[startIndex];
int left = startIndex;
int right = endIndex;
// 退出循環的時候,說明已經檢索到中間位置了
while (left != right){
// 分別去找到左邊和右邊停止的指針
while (left < right && arr[right] > pivot){
right--;
}
while (left < right && arr[left] <= pivot){
left++;
}
// 然後進行交換
if (left < right) {
int p = arr[left];
arr[left] = arr[right];
arr[right] = p;
}
}
// 一輪交換已經結束
// pivot和指針重合點交換
// 將基準值放到所對應的位置
int p = arr[left];
arr[left] = arr[startIndex];
arr[startIndex] = p;
return left;
}
public static void main(String[] args) {
int[] arr = new int[]{4,2,3,6,15,7,1,9};
quickSort(arr,0,arr.length-1);
System.out.println(Arrays.toString(arr));
}
}
希爾排序
- 希爾排序就是分組排序，將取一個間隔gap作為每次分的組數。
package src.datastructure;
import java.util.Arrays;
/**
* @Author: yhy
* @Time: 15:30
* 希爾排序
*/
public class ShellSort {
public static void main(String[] args) {
int[] abc = {1,9,-2,40,33};
// 希爾排序，要進行分組排序，同時依據是gap長度除2，每一次進行交換
// 用到了插入排序和冒泡排序的感覺
// 這是分組
for (int gap = abc.length/2; gap > 0; gap /= 2) {
// 這個for循環寫法要注意
for (int i = gap; i < abc.length; i++) {
int j = i;
int temp = abc[j];
if (abc[j] < abc[j-gap]) {
while (j - gap >= 0 && temp < abc[j-gap]){
abc[j] = abc[j-gap];
j -= gap;
}
//將相對小索引的值變為一開始的
abc[j] = temp;
}
}
}
System.out.println(Arrays.toString(abc));
}
}
歸併排序
- 利用了分治的思想，先分再合來排序。降低問題的難度，逐一突破。
package src.datastructure;
import java.util.Arrays;
/**
* @Author: yhy
* @Time: 0:06
*/
public class MergeSort {
public static void main(String[] args) {
// 自頂向下的歸併排序
int[] abc = {1, 9, -2, 40, 33, 6, 5};
int[] temp = new int[abc.length];
mergeSort(abc, 0, abc.length - 1, temp);
System.out.println(Arrays.toString(abc));
}
// 分加合
public static void mergeSort(int[] arr, int left, int right, int[] temp) {
if (left < right) {
int mid = (left + right) / 2; //中間索引
//向左遞歸進行分解
mergeSort(arr, left, mid, temp);
//向右遞歸進行分解
mergeSort(arr, mid + 1, right, temp);
//合併
merge(arr, left, mid, right, temp);
}
}
// 合方法
public static void merge(int[] arr, int left, int mid, int right, int[] temp) {
int leftStart = left;
int rightStart = mid + 1;
int i = 0;
// 這裡注意可以等於
while (leftStart <= mid && rightStart <= right) {
if (arr[leftStart] >= arr[rightStart]) {
temp[i++] = arr[rightStart++];
} else {
temp[i++] = arr[leftStart++];
}
}
while (leftStart <= mid) {
temp[i++] = arr[leftStart++];
}
while (rightStart <= right) {
temp[i++] = arr[rightStart++];
}
// copy array
i = 0;
int tempLeft = left;
while (tempLeft <= right) {
arr[tempLeft++] = temp[i++];
}
}
}
基數排序
- 用到了十個桶，將每一個數據按照位數將其分割，百、十、個位數進行比較
package com.atguigu.sort;
import java.text.SimpleDateFormat;
import java.util.Arrays;
import java.util.Date;
public class RadixSort {
public static void main(String[] args) {
int arr[] = { 53, 3, 542, 748, 14, 214};
// 80000000 * 11 * 4 / 1024 / 1024 / 1024 =3.3G
// int[] arr = new int[8000000];
// for (int i = 0; i < 8000000; i++) {
// arr[i] = (int) (Math.random() * 8000000); // 生成一個[0, 8000000) 數
// }
radixSort(arr);
System.out.println("基數排序後 " + Arrays.toString(arr));
}
//基數排序方法
public static void radixSort(int[] arr) {
//根據前面的推導過程，我們可以得到最終的基數排序代碼
//1. 得到數組中最大的數的位數
int max = arr[0]; //假設第一數就是最大數
for(int i = 1; i < arr.length; i++) {
if (arr[i] > max) {
max = arr[i];
}
}
//得到最大數是幾位數
int maxLength = (max + "").length();
//定義一個二維數組，表示10個桶, 每個桶就是一個一維數組
//說明
//1. 二維數組包含10個一維數組
//2. 為了防止在放入數的時候，數據溢出，則每個一維數組(桶)，大小定為arr.length
//3. 名明確，基數排序是使用空間換時間的經典算法
int[][] bucket = new int[10][arr.length];
//為了記錄每個桶中，實際存放了多少個數據,我們定義一個一維數組來記錄各個桶的每次放入的數據個數
//可以這裡理解
//比如：bucketElementCounts[0] , 記錄的就是 bucket[0] 桶的放入數據個數
int[] bucketElementCounts = new int[10];
//這裡我們使用循環將代碼處理
for(int i = 0 , n = 1; i < maxLength; i++, n *= 10) {
//(針對每個元素的對應位進行排序處理)， 第一次是個位，第二次是十位，第三次是百位..
for(int j = 0; j < arr.length; j++) {
//取出每個元素的對應位的值
int digitOfElement = arr[j] / n % 10;
//放入到對應的桶中
bucket[digitOfElement][bucketElementCounts[digitOfElement]] = arr[j];
bucketElementCounts[digitOfElement]++;
}
//按照這個桶的順序(一維數組的下標依次取出數據，放入原來數組)
int index = 0;
//遍歷每一桶，並將桶中是數據，放入到原數組
for(int k = 0; k < bucketElementCounts.length; k++) {
//如果桶中，有數據，我們才放入到原數組
if(bucketElementCounts[k] != 0) {
//循環該桶即第k個桶(即第k個一維數組), 放入
for(int l = 0; l < bucketElementCounts[k]; l++) {
//取出元素放入到arr
arr[index++] = bucket[k][l];
}
}
//第i+1輪處理後，需要將每個 bucketElementCounts[k] = 0 ！！！！
bucketElementCounts[k] = 0;
}
}
}
}
- leetcode 347題
package src.datastructure;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
/**
* @Author: yhy
* @Time: 14:37
* leetcode #347
* 用到了桶排序的思想
*/
public class BucketSort {
// Given [1,1,1,2,2,3] and k = 2, return [1,2].
public static void main(String[] args) {
int[] arr = new int[]{1, 1, 1, 2, 2, 3};
int[] a = bucketsort(arr);
System.out.println(Arrays.toString(a));
System.out.println(maxReturn(a,2));
}
// 傳入數組，返回數組
public static int[] bucketsort(int[] arr){
// 定義一個桶
int[] bucket = new int[10];
for (int val: arr ) {
bucket[val]++;
}
return bucket;
}
private static List maxReturn(int[] arr,int k){
int max = arr[0];
List<Integer> list = new ArrayList<>();
while (k >0) {
for (int i = 1; i < arr.length; i++) {
if (max < arr[i]) {
max = arr[i];
arr[i] = 0;
list.add(i);
}
}
max = 0;
k--;
}
return list;
}
}
堆排序
不穩定，線性複雜度，完全二叉樹。
大頂堆
結點大於兩邊子樹，arr[i]>arr[2i+1]&&a[i]>a[2i+2],升序使用這個
package src.datastructure.sort;
import java.util.Arrays;
/**
* @Author: yhy
* @Date: 2020/3/19
* @Time: 12:30
*/
public class HeapSort {
public static void main(String[] args) {
int[] arr = {12, 3, 63, 6, 8};
heapsort(arr);
}
public static void heapsort(int[] arr) {
int temp = 0;
System.out.println("堆排序");
//找到第一個大頂堆結構，然後才可以進行下面的代碼
for (int i = arr.length / 2 - 1; i >= 0; i--) {
adjustHeap(arr, i, arr.length);
}
System.out.println(Arrays.toString(arr));
//交換數據，數組排序 調整堆結構+交換堆頂元素與末尾元素
for (int i = arr.length - 1; i > 0; i--) {
temp = arr[i];
arr[i] = arr[0];
arr[0] = temp;
adjustHeap(arr, 0, i);
}
System.out.println("排序後的" + Arrays.toString(arr));
}
public static void adjustHeap(int[] arr, int i, int length) {
//不斷調整，弄個大頂堆
//後面要進行交換
int temp = arr[i];
//尋找非葉子節點 最後的條件表示左子節點還可以往下尋找
for (int j = i * 2 + 1; j < length; j = j * 2 + 1) {
//左右節點的比較
if (j + 1 < length && arr[j] < arr[j + 1]) {
j++;
}
if (arr[j] > temp) {
arr[i] = arr[j];
i = j;
} else {
break;
}
}
arr[i] = temp;
}
}
小頂堆
結點小於兩邊子樹
思想（藉助樹的結構完成排序）
- 將待排序序列構造成一個大頂堆
- 此時序列的最大值就是堆頂的根節點
- 將其與數組末尾元素交換，這樣構造數組的最大值在右邊
- 再將n-1個元素重新構造一個堆，這樣就會得到n個元素的次小值，反覆進行就可以得到一個有序的數組，完成排序
