# algorithm

**Repository Path**: hiwhy/algorithm

## Basic Information

- **Project Name**: algorithm
- **Description**: 一些简单的测试代码
- **Primary Language**: C
- **License**: Not specified
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 1
- **Forks**: 0
- **Created**: 2019-06-16
- **Last Updated**: 2021-09-28

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

ALGORITHM
====================
排序算法测试
简单的测试,代码有可能不够严谨或存在未知的错误.


## 代码实际测试(不严谨的测试)
* 冒泡排序 (稳定) 		速度最慢
* 快速排序 (不稳定) 		速度平均最快 ,序列越有序越慢, 如很大的序列,但是数据数值范围小.
* 插入排序 (稳定) 		速度比冒泡快两倍多
* 希尔排序 (不稳定)(默认步长) 	速度很快,但是比快速排序慢(两倍左右),数据越大越明显
* 希尔排序 (不稳定)(hibbard) 	速度跟默认步长差不多,疑惑...
* 选择排序 (不稳定)		速度比冒泡快两倍左右,比直接插入排序慢一点点,用这个还不如用插入排序?
* 堆排序   (不稳定)		速度比希尔排序快点
* 基数排序 (稳定)		速度仅次于归并, 数据最大位数比较大的时候效率比希尔排序慢.
* 基数排序 (稳定)(链表实现)	数据量越大越比普通基数排序慢,有待研究.
* 归并排序 (稳定)		速度仅次于快速排序,数值范围较小且排列个数很大的时候比快排要快
## 环境
* ubuntu18.04 (window 下的ubuntu 子系统, 或虚拟机等)

## 编译 (cmake管理)
* ./make.sh

## 运行 (参数为排序的随机数个数)
* cpu : i7 6700
```
./build/test_tools/sort_test  -n 100000000 -d 7
quick_sort              17s:    17110ms:   	17110444us
merge_sort              19s:    19820ms:   	19820072us
radix_sort              28s:    28092ms:   	28092259us
heap_sort               56s:    56574ms:   	56574802us
shell_sort              71s:    71964ms:   	71964163us
radix_linklist_sort2    139s:   139973ms:   	139973427us
```


```
./build/test_tools/sort_test  -n 10000000 -d 7
quick_sort              1s:     1543ms:         1543532us
merge_sort              1s:     1778ms:         1778195us
radix_sort              2s:     2801ms:         2801270us
heap_sort               4s:     4003ms:         4003165us
shell_sort              5s:     5042ms:         5042797us
radix_linklist_sort2    11s:    11532ms:        11532565us

./build/test_tools/sort_test  -n 10000000 -d 3
radix_sort              1s:     1268ms:         1268978us
merge_sort              1s:     1320ms:         1320427us
heap_sort               2s:     2968ms:         2968279us
shell_sort              2s:     2983ms:         2983569us
radix_linklist_sort2    3s:     3921ms:         3921389us
quick_sort              79s:    79280ms:        79280755us  (数值缩小后快排变慢)
```


```
./build/test_tools/sort_test  -n 1000000 -d 7
quick_sort              0s:     133ms:          133657us
merge_sort              0s:     153ms:          153216us
heap_sort               0s:     263ms:          263430us
radix_sort              0s:     285ms:          285582us
shell_sort              0s:     346ms:          346770us
radix_linklist_sort2    0s:     994ms:          994642us

./build/test_tools/sort_test  -n 1000000 -d 3  
merge_sort              0s:     123ms:          123642us
radix_sort              0s:     127ms:          127985us
heap_sort               0s:     230ms:          230044us
shell_sort              0s:     268ms:          268450us
radix_linklist_sort2    0s:     369ms:          369870us
quick_sort              0s:     876ms:          876044us   (数值缩小后快排变慢)
```


```
./build/test_tools/sort_test  -n 100000 -d 7
quick_sort              0s:     10ms:           10627us
merge_sort              0s:     12ms:           12734us
heap_sort               0s:     20ms:           20134us
shell_sort              0s:     25ms:           25675us
radix_sort              0s:     28ms:           28221us
radix_linklist_sort2    0s:     32ms:           32812us

./build/test_tools/sort_test  -n 100000 -d 3
merge_sort              0s:     11ms:   11431us
radix_sort              0s:     11ms:   11894us
quick_sort              0s:     15ms:   15269us
radix_linklist_sort2    0s:     16ms:   16105us
heap_sort               0s:     20ms:   20658us
shell_sort              0s:     21ms:   21209us
```