- #include <stdio.h>
- int ary[10], temp_ary[10];
- void easy_qsort(int, int);
- int main()
- {
- int i;
- for(i=0; i!=10; ++i)
- scanf("%d", &ary[i]);
- easy_qsort(0, 10);
- for(i=0; i!=10; ++i)
- printf("%d ", ary[i]);
- return 0;
- }
- void easy_qsort(int begin, int end)
- {
- int front, back;
- int pivot;
- int i;
- if(begin + 1 >= end)
- return;
- pivot = ary[begin];
- front = begin;
- back = end - 1;
- for(i=begin+1; i!=end; ++i)
- if(ary[i] <= pivot)
- temp_ary[front++] = ary[i];
- else
- temp_ary[back--] = ary[i];
- temp_ary[front] = pivot;
- for(i=begin; i!=end; ++i)
- ary[i] = temp_ary[i];
- easy_qsort(begin, front);
- easy_qsort(front+1, end);
- }
复制代码
快速排序的流程是
如果待排序的数组长度小于等于1,返回
选择轴点,然后把小于轴点的放在轴点左边,大于轴点的放在轴点右边
对轴点两边的数据进行排序
其中难写的部分在于第二部分,如果是其他部分有问题就回头多看几遍书
用一个辅助数组很容易做到第二部分,例如数据
2 7 3 9 5
选择中间点3作为轴点,那么扫描一遍待排序的数据
2比3小,放在辅助数组的最左边;
7比3大,放在辅助数组的最右边;
……
然后再把数据拷贝回来
这样的快速排序叫做非原位快速排序,需要原始数据2倍的内存空间,另外又要多拷贝一次,但是时间复杂度是不变的
真正想把快速排序实现好其实是非常困难的事情,一般可以考虑用标准库中的qsort |