# 排序算法

MarlonBrando1998 2022-01-08 05:01:08 阅读数:600

排序 算法

排序算法

複雜度比較
  • 改圖摘自:菜鳥教程
    在這裏插入圖片描述

冒泡排序

思想
  • 每一輪從左到右,相鄰元素比較,滿足條件則互換比特置。每一輪右側冒出符合條件的一個元素。
  • 如果有n個數據,只需要比較n-1輪。
特點
  • 冒泡排序是穩定的,對於同樣的元素相對比特置是不會改變的。
例子
  • 對(7,10,4,6,3)排序

    第一趟:7,4,6,3,10

    第二趟:4,6,3,7,10

    第三趟:4,3,6,7,10

    第四趟:3,4,6,7,10

實現
@Test
public void test1(){

// 定義一個數組
List<Integer> list = Arrays.asList(1, 10, 3, 4, 6, 7, 8, 2, 3, 0);
Object[] objects = list.toArray();
int[] arr=new int[objects.length];
for (int i = 0; i < objects.length; i++) {

arr[i]= (int) objects[i];
}
// 冒泡法排序
for (int i = 0; i < arr.length; i++) {

// 定義臨時變量並賦值為arr[0]
int temp=arr[0];
for (int j = 0; j < arr.length-1; j++) {

if(arr[j]>arr[j+1]){

temp=arr[j];
arr[j]=arr[j+1];
arr[j+1]=temp;
}
}
System.out.println("第:"+i+":趟"+"========"+temp);
}
System.out.println("===========================");
for (int i = 0; i < arr.length; i++) {

System.out.println(arr[i]);
}
}

選擇排序

思想
  • 在一個長度為N的數組中,第一次遍曆n-1個數找到最小的和第一個交換。
  • 第二次從下一個數開始遍曆n-2個數,找到最小的數和第二個數交換。
  • 重複操作直到n-1次遍曆最小的數和第n-1個數交換。
特點
  • 選擇排序是不穩定的算法
例子
  • 對(7,10,4,6,3)排序

    第一趟:10,7,4,6,3

    第二趟:10,7,4,6,3

    第三趟:10,7,6,4,3

    第四趟:10,7,6,4,3

實現
// 選擇排序
for (int i = 0; i < arr.length; i++) {

// 假設第一個元素是最大的
int max =arr[i];
for (int j = i; j < arr.length; j++) {

if(max<arr[j]){

int temp=arr[j];
arr[j]=max;
max=temp;
}
}
arr[i]=max;
}

快速排序

思想
  • 從數列中挑出一個元素作為基准。
  • 重新排列數列,把比基准小的放在基准前面,反之放在基准後面。
  • 通過遞歸調用把小於基准元素和大於基准元素的子序列進行排序。
  • 分治思想。
例子
  • 對(7,10,4,6,3)排序

    第一趟:3,10,4,6,7

    第二趟:3,10,4,6,7

    第三趟:3,6,4,10,7

    重複執行兩邊的

    ​ 3,4,6,7,10

特點
  • 平均性能好
  • 不穩定,初始序列有序或者基本有序時,時間複雜度下降
實現
@Test
public void test3(){

// 定義一個數組
List<Integer> list = Arrays.asList(1, 10, 3, 4, 6, 7, 8, 2, 3, 0);
Object[] objects = list.toArray();
int[] arr=new int[objects.length];
for (int i = 0; i < objects.length; i++) {

arr[i]= (int) objects[i];
}
// 快速排序:首先獲得一個基准
int low=0;
int high=arr.length-1;
// 定義key用於存放基准,理論上可以拿任何一個數作為基准
int key=arr[low];
for (int i : arr) {

System.out.print(i);
}
System.out.println("排序前===================");
unckSort(arr,low,high);
for (int i : arr) {

System.out.println(i);
}
}
public static int getMiddle(int[] list, int low, int high) {

// 數組的第一個值作為基准值(分界點或關鍵數據)
int tmp = list[low];
while (low < high) {

while (low < high && list[high] >= tmp) {

high--;
}
// 比基准值小的記錄移到低端
list[low] = list[high];
while (low < high && list[low] <= tmp) {

low++;
}
// 比基准值大的記錄移到高端
list[high] = list[low];
}
// 基准值記錄到尾
list[low] = tmp;
// 返回基准值的比特置
return low;
}
public static void unckSort(int[] list,int low,int high) {

if(low < high) {

// 將list數組一分為二
int middle = getMiddle(list,low,high);
// 對低字錶進行遞歸排序
unckSort(list,low,middle-1);
// 對高字錶進行遞歸排序
unckSort(list,middle+1,high);
}
}

插入排序

直接插入排序

思想
  • 從第一個元素開始,如果後面的元素大於前面的元素,則標記該元素為待排序元素。
  • 從後面遍曆已經排好序的元素,如果排好序的元素中最後一個大於待排序的元素,則往後移動有序隊列中的這個元素,依次類推。當條件不滿足時候,將待排序元素放到有序元素隊列的最後面。
特點
  • 插入排序每次插入的比特置都會大於或者等於前一個元素,所以為穩定排序。
例子
  • 排序(3,1,2,5,4)

    第一趟:1,3

    第二趟:1,2,3

    第三趟:1,2,3,5

    第四趟:1,2,3,4,5

實現一
@Test
public void test5(){

// 無序數組
int arr[]={
3,1,2,5,4,7,9,5,2};
int j; // 已排序列錶下標
int num; // 待排序元素
for (int i = 1; i < arr.length; i++) {

if (arr[i] < arr[i - 1]) {

num = arr[i];
// 賦值給待排序元素
for (j = i - 1; j >= 0 && arr[j] > num; j--) {

arr[j + 1] = arr[j];
// 從後往前遍曆已排序列錶,逐個和待排序元素比較,如果已排序元素較大,則將它後移
}
arr[j + 1] = num;
// 將待排序元素插入到正確的比特置
}
}
for (int i = 0; i < arr.length; i++) {

System.out.println(arr[i]);
}
}
實現二
public void sort(int[] arr) {

// 從第二個元素開始
for (int i = 1; i < arr.length; i++) {

if (arr[i] < arr[i - 1]) {

// 當前待排序元素為temp
int temp = arr[i];
int j = i;
// 待排序元素和之前的每個元素做比較
while (j >0 && temp < arr[j - 1]) {

arr[j] = arr[j - 1];
j--;
}
arr[j] = temp;
}
}
}
時間複雜度

最壞情况下,整個數組是倒序的複雜度為O(n^2),最好的情况下整個數組的順序就是想要的結果,時間複雜度為O(n)


希爾排序(三層for循環)

思想

​ 是插入排序的一種,是對直接插入排序的一個優化。

  • 將待排序的數組元素按下標的一定增量分組,分成多個子序列,然後對各個子序列進行直接插入排序。
  • 縮减增量再排序,直到增量為1時,進行最後一次直接插入排序。
實現
public void sort(int[] arr) {

int num;
// temp 為增量
for (int temp = arr.length / 2; temp > 0; temp = temp / 2) {

for (int i = temp; i < arr.length; i++) {

// 增量的數據互相比較交換比特置
for (int j = i; j >= temp; j = j - temp) {

if (arr[j] < arr[j - temp]) {

num = arr[j - temp];
arr[j - temp] = arr[j];
arr[j] = num;
}
}
}
}
}
時間複雜度

最好元素都是有序的:O(n)

最壞和直接插入排序一樣:O(n^2)

版权声明:本文为[MarlonBrando1998]所创,转载请带上原文链接,感谢。 https://gsmany.com/2022/01/202201080501080400.html