《數(shù)據(jù)結構》實驗報告

學號：? 2018329621200 ??	機器號 10-414-28 ?	姓名： 申屠志剛
日期：? 2019/12/18????? ??	程序名：?????? main.cpp???????
實驗內(nèi)容：?? 快速排序???

• 目的和要求（需求分析）：

掌握快速排序的實現(xiàn)方法

掌握快速排序的基本思想

掌握快速排序的時間性能

要求：用快速排序法實現(xiàn)對無序序列的排序

• 程序設計的基本思想，原理和算法描述：

?使用分治策略，將一個序列分為兩個子序列。

步驟：

在待排序的n個記錄中任選一個進行記錄（通常選第一個），作為為基準（分區(qū)標準）。

進行分區(qū)，即：將所有比基準值小的元素放在基準左邊，所有比基準值大的元素放在基準的右邊，中間為所選的基準。

對左右兩個分區(qū)遞歸進行步驟1、2，遞歸結束條件是序列的大小是0或1。

• 調(diào)試和運行程序過程中產(chǎn)生的問題及采取的措施：

無

• 源程序及注釋：

/* *@Author: STZG *@Language: C++ */ #include <bits/stdc++.h> using namespace std; void quickSort(int a[],int low, int high)//a:待排序數(shù)組，low:最低位的下標，high:最高位的下標 {int left=low,right=high;int key=a[left];//用數(shù)組的第一個記錄作為分區(qū)元素if(low>=high)return;while(left!=right){while(left<right&&a[right]>=key)//從右向左掃描，找第一個碼值小于key的記錄，并交換到keyright--;a[left]=a[right];while(left<right&&a[left]<=key)//從左向右掃描，找第一個碼值大于key的記錄，并交換到右邊left++;a[right]=a[left];}a[left]=key;//分區(qū)元素放到正確位置quickSort(a,low,left-1);quickSort(a,left+1,high); } int main() {int a[]={2,6,2,3,5,8,9,1,2,4,5,3};quickSort(a,0,12);for(auto b:a)cout<<b<<endl;//cout << "Hello world!" << endl;return 0; }

• 運行結果

?

• 心得與體會：

通過本次試驗，讓我更深刻理解了快速排序法與其應用，因為快速排序是對冒泡排序的一種改進，所以在冒泡排序的原有基礎上再學習快速排序就顯得不是很困難。

總結

以上是生活随笔為你收集整理的《数据结构与算法》实验报告——快速排序的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。