冒泡排序
冒泡排序是我們能想到的一個最簡單的排序方法，它的思想就是將一個陣列內的數字和相鄰的進行比較，把比較大的放在靠后位置，當從頭到尾比較一遍，我們就可以拿到最大的那個資料了，這樣回圈，每次排除最大的那個，就可以完成排序，
上圖：
代碼實作：（寫法不唯一，可以自己簡化寫出）
public class BubbleSort {
//冒泡，arr：需要排序的陣列，n：需要排序的陣列的長度
public static void Bubble(int[] arr,int n){
for (int i = 0; i < n-1; i++) {
if(arr[i]>arr[i+1]){//如果前面的比后面的大，就交換位置
int temp = arr[i];
arr[i]=arr[i+1];
arr[i+1]=temp;
}
}
}
public static void bubbleSort(int[] arr){
int n = arr.length;
while (n>1){//回圈找出最大的，直到剩下一個數
Bubble(arr, n);
n--;
}
}
public static void main(String[] args) {
int arr[] = {1,4,7,10,8,3,6};
bubbleSort(arr);
for (int i : arr) {
System.out.println(i);
}
}
}
選擇排序
選擇排序的思想就是，我們把我們的需要排序的陣列看成一個已經排序好的陣列和未排序的陣列的組合，初始情況排序好的陣列沒有值，我們對未排序的陣列進行篩選，挑出最大的那個數，然后與未排序最后的那個數進行交換，這個最大的數就放進了已經排好序的陣列中了，
圖解：
代碼實作：
public class SelectSort {
//arr是需要排序的陣列，n是需要排序的陣列長度
//這個方法就是獲取當前需要排序的陣列中最大的值得下標
public static int getMaxIndex(int[] arr, int n) {
int max = arr[0];
int index = 0;
for (int i = 1; i < n; i++) {
if (arr[i] > max) {
max = arr[i];
index = i;
}
}
return index;
}
public static void selectSort(int[] arr) {
int n = arr.length - 1;
while (n > 1) {
//交換未排序的陣列中最大的值與最后一個數的位置
int maxIndex = getMaxIndex(arr, n);
int temp = arr[n];
arr[n] = arr[maxIndex];
arr[maxIndex] = temp;
n--;//交換后，這個最大的數就已經在排好序的陣列中
}
}
public static void main(String[] args) {
int arr[] = {1, 4, 7, 10, 8, 3, 6};
selectSort(arr);
for (int i : arr) {
System.out.println(i);
}
}
}
插入排序
插入排序的思想就是我們把陣列看成一個排好序(初始可能只有一個數)和未排序的陣列的組合，我們在未排序的陣列中取出一個A，在已經排好序的陣列中找到arr[i]，如若arr[i]>A,那么我們就將他放在arr[i]和arr[i-1]這個位置，(如果沒有理解，參考圖片理解）
代碼實體：
public class InsertSort {
public static void insert(int[] arr, int n) {
int key = arr[n];//記下當前需要排序的數
int i = n;
while (arr[i-1]>key){//在找到可以放的位置（小于key）之前，我們就把所有的數往后面”挪“一位
arr[i]=arr[i-1];
i--;
if(i==0){//如果到開頭的位置還沒有出現小于的情況，那么我們就應該將其放在開頭，
break;
}
}
arr[i]=key;
}
public static void insertSort(int arr[]){
for (int i = 1; i < arr.length ; i++) {//默認從1開始，因為第一個數我們默認已經排好序
insert(arr,i);
}
}
public static void main(String[] args) {
int arr[] = {1,4,7,10,8,3,6};
insertSort(arr);
for (int i : arr) {
System.out.println(i);
}
}
}
希爾排序
我們會了插入排序，不妨看看插入排序有哪些缺點？假設一串數字的前面很多都已經是有序的，只有最后的幾個是沒有排序的，比如：{2，3，4，5，6，7，8，9，1}，我們可以看到，只需要把1放在開頭就可以，但是使用插入排序很不理想，
希爾排序的基本思想就是：我們把陣列按照一定增量分成組，每次比較組內的值大小進行插入排序，然后增量逐漸縮小，繼續排序，當我們的增量變為1的時候，所有的數就已經排好序（還是看圖解比較好理解），這樣的好處是，在分組的幾次排序后，我們就將一些較小的數放在了最前面，就不會出現上述例子的情況
代碼實作：
public class ShellSort {
//同樣是插入排序，但是每次排序的都是當前組內的成員
//arr:需要排序的陣列，n：開始排序的位置，gap增量
public static void shellInsert(int[] arr, int n, int gap) {
int key = arr[n];//記下當前需要排序的數
while ( n-gap>=0 && key < arr[n - gap]) {
arr[n] = arr[n - gap];
n -= gap;//尋找下一個組內成員
}
arr[n] = key;
}
public static void shellSort(int[] arr) {
for (int gap = arr.length / 2; gap >0; gap /= 2) {
for (int i = gap; i < arr.length; i++) {
shellInsert(arr,i,gap);
}
System.out.println();
}
}
public static void main(String[] args) {
int arr[] = {2,3,4,5,6,7,8,1};
shellSort(arr);
for (int i : arr) {
System.out.println(i);
}
}
}
快速排序
快速排序是我們最常用并且最快的一種排序演算法，實作起來也很簡單，但有點難理解，其主要思想就是我們在陣列中找到一個基準數，然后對陣列的左右兩邊進行遍歷，找到一個比基準數大的數和一個比基準數小的數，將兩個數換位，這樣一輪回圈下來，當左右兩個指標相遇的時候，左邊都是比基準數小的數，右邊的都是比基準數大的數，然后我們對左右兩邊再遞回運算，最后將所有的數都進行了排序，（話不多說，看圖理解）
步驟簡述：
我們的中心思想就是把比基準數大的放在基準數右邊，比基準數小的放在基準數左邊
1、定義left，right，基準數base=arr[left]
2、先從right開始找，找到一個比base小的樹，在開始從left開始找比base大的(如果我們從左邊先開始找，那么我們的基準數就得是arr[right]，否則我們進行第3步的時候，交換后可能會把一個比基準數大的交換到left位置，這樣就無法繼續操作)
3、當指標相遇的時候，我們交換指標位置和基準數的位置
4、此時新的基準數產生(指標相遇位置的數）
5、調整left和right，遞回執行上述步驟
public class QuickSort {
public static void quickSort(int[] arr, int left, int right) {
//如果左邊邊界大于右邊，就return
if (left >= right) {
return;
}
int l = left;//用于標識左邊指標
int r = right;// 用于標識右邊指標
int base = arr[left];//記錄基準數
//判斷指標有沒有相遇
while (l != r) {
while (arr[r] >= base && r > l) {//先從右往左找出比基準數小的數
r--;
}
while (arr[l] <= base && l < r) {//再從左向右找出比基準數大的數
l++;
}
//交換
int temp = arr[l];
arr[l] = arr[r];
arr[r] = temp;
}
//當指標相遇時，交換基準數和指標的位置，此時指標位置就是基準數，指標左邊的都不大于基準數，右邊的都不小于基準數
arr[left] = arr[l];
arr[l] = base;
//遞回呼叫，將左邊所有的數的進行排序
quickSort(arr, left, l - 1);
//右邊的排序
quickSort(arr, r + 1, right);
}
public static void main(String[] args) {
int[] arr ={4, 1, 7, 6, 8, 3, 10};
int left = 0;
int right = arr.length - 1;
quickSort(arr, left, right);
for (int i : arr) {
System.out.println(i);
}
}
}
歸并排序：
在學習歸并排序之前，我們先看一個例子，如果一個陣列{2，5，8，9，1，3，4，7}，這個陣列的特點是前半部分和后半部分都是有序的，我們對他進行排序，那么我們就把它分成兩個有序的陣列，然后通過對比，將較小的放進陣列中，最終就得到了一個有序的陣列，這個思想就是歸并
那么我們就先把這個例子用圖解的形式分析一下，然后代碼實作，當我們完成下面的例子后，就可以著手去實作任意情況的陣列的歸并排序，
實作代碼：
public class MergeSort {
/**
* @param arr 傳入陣列
* @param l 左邊起始位置下標
* @param r 最右邊下標
* @param m 中間點
*/
public static void Merge(int[] arr, int l, int r, int m) {
int LEFT_SIZE = m - l;
int RIGHT_SIZE = r - m + 1;
//創建兩個陣列存
int[] left = new int[LEFT_SIZE];
int[] right = new int[RIGHT_SIZE];
for (int i = l; i < m; i++) {
left[i-l] = arr[i];
}
for (int i = m; i <= r; i++) {
right[i-m] = arr[i];
}
//通過上述步驟，我們就可以把陣列分成兩個有序的陣列，分別存放在兩個不同的陣列中
int i=0,j=0,k=l;//定義三個指標，分別代表left陣列、right陣列、arr陣列的初始指標
while(i<LEFT_SIZE && j<RIGHT_SIZE ){//如果兩邊都沒有到陣列邊界
if(left[i]<right[j]){//我們比較兩個位置，將較小的放在陣列的位置
arr[k]=left[i];
k++;i++;
}
else {
arr[k]=right[j];
k++;j++;
}
}
//出了上述回圈，但是仍然存在可能有陣列中的數沒有放完的情況，我們直接按照順序放入即可，
while (i<LEFT_SIZE){
arr[k]=left[i];
k++;i++;
}while (j<RIGHT_SIZE){
arr[k]=right[j];
k++;j++;
}
}
public static void main(String[] args) {
int[] arr = {2, 5, 8, 9, 1, 3, 4, 7};
int l = 0;
int r =arr.length-1;
int mid =arr.length/2;
Merge(arr, l, r,mid);
for (int i : arr) {
System.out.println(i);
}
}
}
這樣我們就把這個陣列排好序了，
這個時候就有人問了：你這剛好兩邊都是有序的，現實中可不是這樣，
那我們想想，其他混亂一點的陣列可以使用歸并嗎？
答案當然是可以
如果有一定經驗的小伙伴，肯定已經想到了分治，在上述案例中，我們是把資料砍成兩段，每段都是有序的，那么給出一個混亂的資料，我們遞回的去砍，到最后砍的兩邊各剩一個數，那么它不就是上述情況了？就好比{5，3}，我們砍一下{3}、{5}，使用歸并，自然就是{3，5}了，如果還不明白，我們接著看圖
用代碼實作它：
public static void Merge(int[] arr, int l, int r, int m) {
int LEFT_SIZE = m - l;
int RIGHT_SIZE = r - m + 1;
//創建兩個陣列存
int[] left = new int[LEFT_SIZE];
int[] right = new int[RIGHT_SIZE];
for (int i = l; i < m; i++) {
left[i-l] = arr[i];//注意 此時的left[i-l]不能寫arr[i],因為在遞回中l的動態變化的，如果寫死的話，可能出現角標例外的情況
}
for (int i = m; i <= r; i++) {
right[i-m] = arr[i];
}
//通過上述步驟，我們就可以把陣列分成兩個有序的陣列，分別存放在兩個不同的陣列中
int i=0,j=0,k=l;//定義三個指標，分別代表left陣列、right陣列、arr陣列的初始指標
while(i<LEFT_SIZE && j<RIGHT_SIZE ){//如果兩邊都沒有到陣列邊界
if(left[i]<right[j]){//我們比較兩個位置，將較小的放在陣列的位置
arr[k]=left[i];
k++;i++;
}
else {
arr[k]=right[j];
k++;j++;
}
}
//出了上述回圈，但是仍然存在可能有陣列中的數沒有放完的情況，我們直接按照順序放入即可，
while (i<LEFT_SIZE){
arr[k]=left[i];
k++;i++;
}while (j<RIGHT_SIZE){
arr[k]=right[j];
k++;j++;
}
}
public static void mergeSort(int[] arr,int l,int r){
if(l==r){
return;
}else {
int m=(l+r)/2;
mergeSort(arr, l, m);
mergeSort(arr, m+1, r);
Merge(arr,l,r,m+1);
}
}
public static void main(String[] args) {
int[] arr = {1, 4, 7, 10, 8, 3, 6, 5};
int l = 0;
int r =arr.length-1;
mergeSort(arr, l, r);
for (int i : arr) {
System.out.println(i);
}
}
}
成功！
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/177354.html
標籤：其他