演算法【快速排序】

来源:https://www.cnblogs.com/wangsiyaoa/archive/2023/12/07/17883902.html
-Advertisement-
Play Games

從0到1,手把手帶你開發一款截屏工具ScreenCap,001版本,實現基本的截圖功能,實現全屏截圖,實現局部截圖,實現保存截圖,實現截圖另存為 ...


演算法【快速排序】

快速排序。選擇一個作為比較的元素,這裡我們選擇首元素,這個元素我叫他‘比較元素’;前後兩個指針(其實是索引變數)同時往後和往前進行遍歷,開頭的指針遇到比‘比較元素’大的元素停下來(空迴圈體的迴圈即可實現),末尾的指針往前遍歷,遇到比‘比較元素’小的元素停下來;兩個元素都停止後,交換兩個元素,交換後通過外面的大迴圈繼續讓指針運動起來;當兩個指針相遇或交錯時,退出大迴圈;之後將從後面跑來的指針的元素與‘比較元素(首元素)’交換(因為這時這個從後面跑來的指針一定指向小於或等於首元素的元素),這樣可以保證後面跑來的這個指針的位置元素,前面都是小於它的元素,後面都是大於它的元素;之後前面的進行遞歸,後面的也進行遞歸,遞歸的出口是開始的指針大於等於結束的指針(這個開始和結束的指針是上一個大的部分傳來的)。

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define N 10

/**
 *  快排
*/

void quick_sort(int *arr, int size);
void recursion(int *arr, int start, int end);

// 快排
void quick_sort(int *arr, int size){
    recursion(arr, 0, size-1);
}


// 快排的遞歸邏輯
void recursion(int *arr, int start, int end){

    // 第一個作為比較的元素
    int comElement = arr[start];
    // 後面首元素的下標和尾元素的下標都要改變,現在先記錄一下。
    int start_temp = start;
    int end_temp = end;

    if(start_temp <= end_temp){
        while(1){
        // 移動前後兩個下標
        while(start<=end_temp && comElement > arr[++start]);    // 前下標沒有移動到最後且該位置元素大於比較元素時持續後移。即前下標超過末尾或元素大於等於比較元素時停止後移
        while(end >=start_temp && comElement < arr[end--]);     // 後元素小於起始元素 或 該位置元素小於等於比較元素時停止後移
        end++;      // 將最後往前移多的下標加上。

        if(start >= end) break;     // 後位置大於前位置,不進行交換

        // 這裡不能使用異或 或者 相加 的方式交換, 因為可能操作的是同一個元素。
        int temp = arr[start];
        arr[start] = arr[end];
        arr[end] = temp;
        }

        int temp = arr[start_temp];
        arr[start_temp] = arr[end];
        arr[end] = temp;

        static int x_20231217 = 1;
        printf("第%d趟排序結果為:\t", x_20231217++);
        for(int i = 0; i<N; i++) printf("%d\t", arr[i]);
        printf("\n");

        // 遞歸
        recursion(arr, start_temp,end-1);   // end 的位置是之前 比較元素 的那個位置
        recursion(arr, end+1, end_temp);
	}

    
}


int main(int argc, char const *argv[]){

    // 生成隨機種子
    srand(time(0));

    int arr[N];
    for(int i = 0; i<N; i++) arr[i] = rand()%10 + 1;

    printf("原始數據為:\t\t");
    // 列印原始數據
    for(int i = 0; i<N; i++) printf("%d\t", arr[i]);
    printf("\n");

    // 調用快速排序
    quick_sort(arr, N);

    printf("最終數據為:\t\t");
    // 列印排序後的數據
    for(int i = 0; i<N; i++) printf("%d\t", arr[i]);
    printf("\n");

    getchar();
    return 0;
}

您的分享是我們最大的動力!

-Advertisement-
Play Games
更多相關文章
  • React Zombie Child 是指在 React 組件中的一個常見問題。當一個父組件被銷毀時,它的子組件可能仍然存在於記憶體中,這些子組件被稱為“僵屍子組件”。 這種情況通常發生在非同步操作中,例如在父組件中發起了一個非同步請求,而在請求完成之前,父組件被銷毀了。但是,由於非同步請求的回調函數仍然存 ...
  • 在工作中有時候需要單獨設置某個 el-input 組件的內部樣式,比如 字體顏色、背景色、寬度、高度等,這時就需要修改 el-input 組件的內部自帶樣式,修改方式如下: 修改前: el-input 獨占滿一整行 修改後: 模板代碼 <div class="elinput"> <el-input ...
  • 廢話不多說,先看效果再上代碼 一、效果圖 二、html內容 我這裡用來外部樣式表導入css,當然你可以根據自己的喜好 <!DOCTYPE html> <html> <head> <meta charset="utf-8" /> <title>導航欄</title> <!--導入外部樣式表--> <l ...
  • 1、業務需求 需要加一個按鈕,調用第三方API,按鈕十分鐘之內只能點擊一次,刷新頁面也只能點擊一次 2、思路 加一個本地緩存的時間戳,通過時間戳計算指定時間內不能點擊按鈕 3、實現 1)vue頁面 <template> <el-row :gutter="15"> <el-col :span="4"> ...
  • 在頁面佈局中,我們經常會遇到/使用這麼一類常見的佈局,也就是列表內容水平居中於容器中,像是這樣: <ul class="g-contaner"> <li></li> <li></li> </ul> ul { width: 500px; display: flex; flex-direction: r ...
  • 專欄分享:vue2源碼專欄,vue3源碼專欄,vue router源碼專欄,玩具項目專欄,硬核💪推薦🙌 歡迎各位ITer關註點贊收藏🌸🌸🌸 語法 傳入一個 getter 函數,返回一個預設不可手動修改的 ref 對象 const count = ref(1) const plusOne = ...
  • 快速啟動SpringBoot項目,包括引入spring-boot-starter-parent,@SpringBootApplication入口類註解、自動保存刷新pom.xml ...
  • Docker,一種可以將軟體打包到容器中併在任何環境中可靠運行的工具。但什麼是容器以及為什麼需要容器呢?今天就來一起學快速入門一下Docker吧!希望本文對您有所幫助。 假設您使用 Cobol 構建了一個在某種奇怪風格的 Linux 上運行的應用程式。您想與您的朋友分享這個應用程式,但他有一個完全不 ...
一周排行
    -Advertisement-
    Play Games
  • 隨著Aspire發佈preview5的發佈,Microsoft.Extensions.ServiceDiscovery隨之更新, 服務註冊發現這個屬於老掉牙的話題解決什麼問題就不贅述了,這裡主要講講Microsoft.Extensions.ServiceDiscovery(preview5)以及如何 ...
  • 概述:通過使用`SemaphoreSlim`,可以簡單而有效地限制非同步HTTP請求的併發量,確保在任何給定時間內不超過20個網頁同時下載。`ParallelOptions`不適用於非同步操作,但可考慮使用`Parallel.ForEach`,儘管在非同步場景中謹慎使用。 對於併發非同步 I/O 操作的數量 ...
  • 1.Linux上安裝Docken 伺服器系統版本以及內核版本:cat /etc/redhat-release 查看伺服器內核版本:uname -r 安裝依賴包:yum install -y yum-utils device-mapper-persistent-data lvm2 設置阿裡雲鏡像源:y ...
  • 概述:WPF界面綁定和渲染大量數據可能導致性能問題。通過啟用UI虛擬化、非同步載入和數據分頁,可以有效提高界面響應性能。以下是簡單示例演示這些優化方法。 在WPF中,當你嘗試綁定和渲染大量的數據項時,性能問題可能出現。以下是一些可能導致性能慢的原因以及優化方法: UI 虛擬化: WPF提供了虛擬化技術 ...
  • 引言 上一章節介紹了 TDD 的三大法則,今天我們講一下在單元測試中模擬對象的使用。 Fake Fake - Fake 是一個通用術語,可用於描述 stub或 mock 對象。 它是 stub 還是 mock 取決於使用它的上下文。 也就是說,Fake 可以是 stub 或 mock Mock - ...
  • 為.net6在CentOS7上面做準備,先在vmware虛擬機安裝CentOS 7.9 新建CentOS764位的系統 因為CentOS8不更新了,所以安裝7;簡單就一筆帶過了 選擇下載好的操作系統的iso文件,下載地址https://mirrors.aliyun.com/centos/7.9.20 ...
  • 經過前面幾篇的學習,我們瞭解到指令的大概分類,如:參數載入指令,該載入指令以 Ld 開頭,將參數載入到棧中,以便於後續執行操作命令。參數存儲指令,其指令以 St 開頭,將棧中的數據,存儲到指定的變數中,以方便後續使用。創建實例指令,其指令以 New 開頭,用於在運行時動態生成並初始化對象。方法調用指... ...
  • LiteDB 是一個輕量級的嵌入式 NoSQL 資料庫,其設計理念與 MongoDB 類似,但它是完全使用 C# 開發的,因此與 C# 應用程式的集成非常順暢。與 SQLite 相比,LiteDB 提供了 NoSQL(即鍵值對)的數據存儲方式,並且是一個開源且免費的項目。它適用於桌面、移動以及 We ...
  • 1 開源解析和拆分文檔 第三方的工具去對文件解析拆分,去將我們的文件內容給提取出來,並將我們的文檔內容去拆分成一個小的chunk。常見的PDF word mark down, JSON、HTML。都可以有很好的一些模塊去把這些文件去進行一個東西去提取。 優勢 支持豐富的文檔類型 每種文檔多樣化選擇 ...
  • OOM是什麼?英文全稱為 OutOfMemoryError(記憶體溢出錯誤)。當程式發生OOM時,如何去定位導致異常的代碼還是挺麻煩的。 要檢查OOM發生的原因,首先需要瞭解各種OOM情況下會報的異常信息。這樣能縮小排查範圍,再結合異常堆棧、heapDump文件、JVM分析工具和業務代碼來判斷具體是哪 ...