算法學習(排序算法)

第一章 排序算法

---

提示：寫完文章后，目錄可以自動生成，如何生成可參考右邊的幫助文檔

文章目錄

• 算法學習(排序算法)
• 前言
• 一、快速排序
• 二、快速排序
• • 1.基本思路(流程)
  • 2.快排3.0版本

---

前言

提示：這里可以添加本文要記錄的大概內容：

例如：隨著人工智能的不斷發展，機器學習這門技術也越來越重要，很多人都開啟了學習機器學習，本文就介紹了機器學習的基礎內容。

---

提示：以下是本篇文章正文內容，下面案例可供參考

一、快速排序

在看快速排序之前,先看一個荷蘭國旗問題:

給定一個整數數組和一個值M（存在于原數組中），要求把數組中小于M的元素放到數組的左邊，等于M的元素放到數組的中間，大于M的元素放到數組的右邊，最終返回一個整數數組，只有兩個值，0位置是等于M的數組部分的左下標值、1位置是等于M的數組部分的右下標值。

進行通用一點的解釋
給定數組arr，將[l, r]范圍內的數（當然默認是 [ 0 - arr.length - 1 ]），小于M放到數組左邊，等于M放到數組中間，大于M放到數組右邊。最后返回等于arr[r]的左, 右下標值。
以M=5為例

實現代碼

import java.util.Scanner;public class Main {public static void main(String[] args) {int arr[]={1,5,4,3,2,8,6,3,0};partition(arr,0,arr.length-1,3);for (int i = 0; i < arr.length; i++) {System.out.print(arr[i]+" ");}}public static void partition(int[] arr,int L,int R,int M){int less=L-1; //限定比比較元素小的范圍(起始在0之前)int more=R+1;//限定比比較元素大的范圍(起始在最后一個元素之后)while(L<more){ //當遍歷到大元素的范圍就停止if(arr[L]<M){ //若當前元素比比較元素小// 則將當前元素與小元素范圍的后一個元素交換,并將小元素范圍擴大int temp=arr[L];arr[L]=arr[++less];L++;arr[less]=temp;}else if(arr[L]>M){//若當前元素比比較元素大// 則將當前元素與大元素范圍的前一個元素交換,并將大元素范圍擴大//注意:此時因為交換了元素,所以并不移動Lint temp=arr[L];arr[L]=arr[--more];arr[more]=temp;}else{//等于情況,移到下一位L++;}}} }

二、快速排序

1.基本思路(流程)

首先設定一個分界值，通過該分界值將數組分成左中右三部分。

同荷蘭國旗問題類似,將小于分界值的數集中至數組的中間,大于分界值的數據集中到數組右邊

然后,左右兩邊的數據可以作為一個數組單獨排序,同樣是按1的方法進行排序

2.快排3.0版本

快排1.0和2.0當遇到最差情況(1,2,3,4,5,6,7,8,9),復雜度會到O(n^2)
快排3.0可以穩定在O(n*logn)

隨機將數組中的某個數放到比較位置,即最右側位置

調用荷蘭國旗方法,拿到大小區的下標

大小區各自作為數組進行荷蘭國旗方法

進行遞歸,最后拿到一個拍好序的數組

代碼如下：

import java.util.Scanner;public class Main {public static void main(String[] args) {int arr[]={1,5,4,3,2,8,6,3,0};quickSort(arr, 0, arr.length-1);for (int i = 0; i < arr.length; i++) {System.out.print(arr[i]+" ");}}public static void quickSort(int[] arr,int L,int R){if( L<R ){ //左右指針沒有重疊證明還可以分//隨機選出一個數與末尾元素進行交換int temp = (int) Math.random() * (R-L+1);int t=arr[L+temp];arr[L+temp] = arr[R];arr[R] = t;//拿到排序出來的下標int[] p=partition(arr, L, R);//遞歸,左右兩邊進行quickSort(arr, L, p[0]);quickSort(arr, p[1], R);}}public static int[] partition(int[] arr,int L,int R){int less=L-1; //限定比比較元素小的范圍(起始在0之前)int more=R;//限定比比較元素大的范圍while(L<more){ //當遍歷到大元素的范圍就停止if(arr[L]<arr[R]){ //若當前元素比比較元素小// 則將當前元素與小元素范圍的后一個元素交換,并將小元素范圍擴大int temp=arr[L];arr[L]=arr[++less];L++;arr[less]=temp;}else if(arr[L]>arr[R]){//若當前元素比比較元素大// 則將當前元素與大元素范圍的前一個元素交換,并將大元素范圍擴大//注意:此時因為交換了元素,所以并不移動Lint temp=arr[L];arr[L]=arr[--more];arr[more]=temp;}else{//等于情況,移到下一位L++;}}//交換more位置的元素和R位置的元素,more后移一位int temp=arr[R];arr[R] = arr[more];arr[more]=temp;//將小元素的結束下標和大元素的開始下標(加一是以為有交換)返回return new int[] {less,more+1};} }

總結

以上是生活随笔為你收集整理的荷兰国旗问题+快速排序的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。