数据结构算法学习-排序-快速排序
排序
将一组有顺序的元素按大小(只要定义可以返回true或false的比较关系,非一定数值比较)重新调整顺序。
快速排序
快速排序类似归并排序,不过归并排序是依次将数组长度(1,2...n/4,n/2,n)内的元素排序合并,既先将小范围内排序(2,4,8...),然后按插入排序将数组归并;快速排序先将大范围排序分为两部分(中间点P,左边arr[L] <= arr[P] <= 右边arr[R]),然后小范围内递归该过程。
算法实现
/* Elr Sort Quick Source */ #include <stdio.h> #include <stdlib.h> #include "elr_sort_quick.h" void exchange(long long int* arr, int p1, int p2) { long long int tmp = arr[p1]; arr[p1] = arr[p2]; arr[p2] = tmp; } int partition(long long int* arr, int left, int right) { long long int tmp = arr[right]; int i = left - 1; int j; for (j = left; j < right; j++) { if (arr[j] <= tmp) { i++; exchange(arr, i, j); } } exchange(arr, i + 1, right); return i + 1; } void quickSort(long long int* arr, int left, int right) { if (left < right) { int sep = partition(arr, left, right); printf("left:%d,right:%d,position:%lld,partition:%d ", left, right, arr[sep], sep); int i; for (i = left; i <= right; i++) { printf("%lld ", arr[i]); } printf("\n"); quickSort(arr, left, sep - 1); quickSort(arr, sep + 1, right); } } long long int* elrSortQuick(long long int* arr, int len) { quickSort(arr, 0, len - 1); return arr; }
调试调用
#include <stdio.h> #include <stdlib.h> #include "elr_sort_quick.h" int main(int argc, char **argv){ int i; long long int arr[] = {6, 2, 4, 1, 3, 5, 0, 8, 9, 7}; elrSortQuick(arr, 10); printf("%d\n", (int)(sizeof(arr) / sizeof(long long int))); for (i = 0; i < 10; i++) { printf("%lld ", arr[i]); } printf("\n"); return 0; }
输出
left:0,right:9,position:7,partition:7 6 2 4 1 3 5 0 7 9 8 left:0,right:6,position:0,partition:0 0 2 4 1 3 5 6 left:1,right:6,position:6,partition:6 2 4 1 3 5 6 left:1,right:5,position:5,partition:5 2 4 1 3 5 left:1,right:4,position:3,partition:3 2 1 3 4 left:1,right:2,position:1,partition:1 1 2 left:8,right:9,position:8,partition:8 8 9 10 0 1 2 3 4 5 6 7 8 9
相关推荐
Masimaro 2020-06-21
清溪算法君老号 2020-06-01
田有朋 2020-04-19
cmsmdn 2020-03-03
Joymine 2020-06-06
GhostLWB 2020-04-20
sunjunior 2020-04-10
shenwenjie 2020-02-26
sunjunior 2020-02-15
hanyujianke 2020-01-13
路漫 2020-01-12
sunnyJam 2019-12-31
KilluaZoldyck 2019-12-15
yuanran0 2019-12-14
Happyunlimited 2019-12-10
baike 2019-12-09
yishujixiaoxiao 2019-12-02
YUAN 2019-11-19