最简洁的快速排序

北美农民 发表于 2013-11-19 03:35
int a = Integer.MAX_VALUE - 10;
    int b = Integer.MAX_VALUE - 1;
    int c;

你说的对。。。我刚一直把“溢出”理解成了indexOufOfBound

北美农民 发表于 2013-11-10 05:17
LZ这里可以用， 但建议不要用。 因为很多时候不知道swap会不会是针对同一个引用进行， 这样就变0 了。比如 ...

原来还可以这样swap，学习了！

1. int partion(vector<int>& nums, int left, int right) {
   
2.     int pivot = nums[left], low = left;
   
3.     while (left < right) { //
   
4.         while (left < right && nums[right] >= pivot) right--;
   
5.         while (left < right && nums[left] <= pivot) left++;
   
6.         swap(nums[left], nums[right]);
   
7.     }
   
8.     swap(nums[left], nums[low]);
   
9.     return left;
   
10. }
    
11. 
    
12. void quickSort(vector<int>& nums, int left, int right) {
    
13.     if (left >= right) return;
    
14.     int pos = partion(nums, left, right);
    
15.     quickSort(nums, left, pos - 1);
    
16.     quickSort(nums, pos + 1, right);
    
17. }

复制代码

北美农民 发表于 2013-11-10 04:12
快排什么版本都见过， 我就写这种。 不见得比我简洁吧.

确实 我也只有这种能写对了

EroicaCMCS 发表于 2013-11-9 19:45
效率和可读性之间要取舍啊，最近也很犹豫这个问题。。
据说业界先写成可读性高的代码，然后改写，把长的 ...

变量名对C语言运行效率没有任何影响。何来取舍之说？目前只有js习惯干这种事情，但js这么做是为了减少源文件的大小，让网页加载更快。C这种编译语言需要刻意把变量名取成1个字母只能损害可读性

1. void quick_sort(int a[], int first, int last) {
   
2.     if (first < last) {
   
3.         int pivot = a[last], p_idx = first - 1;
   
4. 
   
5.         for (int i = first; i <= last; ++i)
   
6.             if (a[i] <= pivot || i == last) {
   
7.                 int temp = a[++p_idx];
   
8.                 a[p_idx] = a[i];
   
9.                 a[i] = temp;
   
10.             }
    
11. 
    
12.         quick_sort(a, first, p_idx - 1);
    
13.         quick_sort(a, p_idx + 1, last);
    
14.     }
    
15. }

复制代码

这样行吗？

yabirthday 发表于 2020-5-3 15:58
[mw_shl_code=cpp,true]int partion(vector& nums, int left, int right) {
    int pivot = nums[left],  ...

挑个小刺，partition拼错了~