```mermaid graph TD A[开始] --> B{是否有元素 需要交换} B -- 是 --> C[交换相邻元素] C --> B B -- 否 --> D[排序完成] ```
2.1B Stata 代码实例
clear input number 4 7 2 3 end
* 显示原始数据 list
* 冒泡排序算法 forvalues i = 1/3 { forvalues j = 1/`=4-`i'' { quietly { sum number in `j'/`=`j'+1' if r(min) != number[`j'] { local temp = number[`j'] replace number = number[`j'+1] in `j' replace number = `temp' in `=`j'+1' } } } }
```mermaid graph LR A[开始] --> B[取下一 个元素] B --> C{比已排序 部分的最后 一个元素小?} C -- 是 --> D[移动元素] D --> C C -- 否 --> E[插入到 正确位置] E --> F{还有未排 序元素?} F -- 是 --> B F -- 否 --> G[排序完成] ```
2.3B Stata 代码实例
clear input number 4 7 2 3 end
* 显示原始数据 list
* 插入排序算法 forvalues i = 2/4 { quietly { local key = number[`i'] //保存当前要排序的元素 local j = `=`i'-1' //向前遍历已排序部分并找到合适位置。 while `j' > 0 & number[`j'] > `key' { replace number = number[`j'] in `=`j'+1' //将元素后移 local j = `=`j'-1' } replace number = `key' in `=`j'+1' //将当前元素插入到合适位置 } }
```mermaid graph LR A[开始] --> B[选择 基准元素] B --> C[划分为左右 两个子数组] C --> D[递归排序 左子数组] D --> E[递归排序 右子数组] E --> F[排序完成] ```
2.4B Stata 代码实例
clear input number 4 7 2 3 end
* 显示原始数据 list
* 快速排序算法 cap prog drop quicksort program define quicksort syntax varname, from(numlist) to(numlist) local left = `: word 1 of `from'' local right = `: word 1 of `to'' if `left' < `right' { local pivot = `left' local i = `left' local j = `right' while `i' < `j' { while `i' <= `right' & number[`i'] <= number[`pivot'] {
local i = `=`i'+1' } while number[`j'] > number[`pivot'] { local j = `=`j'-1' } if `i' < `j' { local temp = number[`i'] replace number = number[`j'] in `i' replace number = `temp' in `j' } } local temp = number[`pivot'] replace number = number[`j'] in `pivot' replace number = `temp' in `j' quicksort number, from(`left') to(`=`j'-1') quicksort number, from(`=`j'+1') to(`right') } end
*--------------------------begin---- cap prog drop bubblesort program define bubblesort syntax varname local n = _N forvalues i = 1/`=`n'-1' { forvalues j = 1/`=`n'-`i'' { if `varlist'[`j'] > `varlist'[`=`j'+1'] { local temp = `varlist'[`j'] replace `varlist' = `varlist'[`=`j'+1'] in `j' replace `varlist' = `temp' in `=`j'+1' } } } end *---------------------------over----
B. 选择排序程序
cap prog drop selectionsort program define selectionsort syntax varname local n = _N forvalues i = 1/`=`n'-1' { local min_idx = `i' forvalues j = `=`i'+1'/`n' { if `varlist'[`j'] < `varlist'[`min_idx'] { local min_idx = `j' } } if `min_idx' != `i' { local temp = `varlist'[`i'] replace `varlist' = `varlist'[`min_idx'] in `i' replace `varlist' = `temp' in `min_idx' } } end
C. 插入排序程序
cap prog drop insertionsort program define insertionsort syntax varname local n = _N forvalues i = 2/`n' { local key = `varlist'[`i'] local j = `=`i'-1' while `j' > 0 & `varlist'[`j'] > `key' { replace `varlist' = `varlist'[`j'] in `=`j'+1' local j = `=`j'-1' } replace `varlist' = `key' in `=`j'+1' } end
D. 快速排序程序
cap prog drop quicksort program define quicksort syntax varname, from(numlist) to(numlist) local left = `: word 1 of `from'' local right = `: word 1 of `to'' if `left' < `right' { local pivot = `left' local i = `left' local j = `right' while `i' < `j' { while `i' <= `right' & `varlist'[`i'] <= `varlist'[`pivot'] { local i = `=`i'+1' } while `varlist'[`j'] > `varlist'[`pivot'] { local j = `=`j'-1' } if `i' < `j' { local temp = `varlist'[`i'] replace `varlist' = `varlist'[`j'] in `i' replace `varlist' = `temp' in `j' } } local temp = `varlist'[`pivot'] replace `varlist' = `varlist'[`j'] in `pivot' replace `varlist' = `temp' in `j' quicksort `varlist', from(`left') to(`=`j'-1') quicksort `varlist', from(`=`j'+1') to(`right') } end
4.2 耗时测试
clear set seed 135 set obs 30 gen number = floor(runiform() * 100) global reps = 50
* 冒泡排序耗时测试 timer clear 1 timer on 1 forvalues i = 1/$reps{ qui bubblesort number } timer off 1 timer list 1
* 选择排序耗时测试 timer clear 2 timer on 2 forvalues i = 1/$reps{ qui selectionsort number } timer off 2 timer list 2
* 插入排序耗时测试 timer clear 3 timer on 3 forvalues i = 1/$reps{ insertionsort number } timer off 3 timer list 3
* 快速排序耗时测试 timer clear 4 timer on 4 local N = _N forvalues i = 1/$reps{ qui quicksort number, from(1) to(`N') } timer off 4 timer list 4
