最简洁的快速排序

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

第6行直接(left + right) / 2就行了嘛

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

能举个(left + right) / 2和越界的例子吗？

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

int pivot = a[(left + right) / 2];
这个怎么会溢出？就算左右同时是上届除以二也不会溢出吧

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

1. 我是真自己试过才回帖的，有那种情况会溢出您给个edge case？

复制代码

1. package Sorting;
   
2. import java.util.*;
   
3. 
   
4. public class test {
   
5.        
   
6.         public static void main(String[] arg) throws Exception{
   
7. 
   
8.                 Random myRandom = new Random();
   
9.                 QuickSortTest myQuicksort = new QuickSortTest();
   
10.                
    
11.                 // Test 1000 times
    
12.                 for(int i = 0; i < 1000; i++){
    
13.                         // Create a random array
    
14.                         int[] toTest = new int[10];
    
15.                         for(int k = 0; k < 10; k++){
    
16.                                 toTest[k] = myRandom.nextInt(100);
    
17.                         }
    
18.                         System.out.println("Before: " + Arrays.toString(toTest));
    
19.                         myQuicksort.qsort(toTest);
    
20.                         System.out.println("After: " + Arrays.toString(toTest) + "\n");
    
21.                 }
    
22.                
    
23.                 // Test edge cases
    
24.                 int[] toTest = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
    
25.                 System.out.println("Before: " + Arrays.toString(toTest));
    
26.                 myQuicksort.qsort(toTest);
    
27.                 System.out.println("After: " + Arrays.toString(toTest) + "\n");
    
28.                
    
29.                 int[] toTest2 = {9, 8, 7, 6, 5, 4, 3, 2, 1, 0};
    
30.                 System.out.println("Before: " + Arrays.toString(toTest2));
    
31.                 myQuicksort.qsort(toTest);
    
32.                 System.out.println("After: " + Arrays.toString(toTest2) + "\n");
    
33.                
    
34.                 int[] toTest3 = {1, 1, 1, 1, 1, 1, 1, 1, 1, 1};
    
35.                 System.out.println("Before: " + Arrays.toString(toTest3));
    
36.                 myQuicksort.qsort(toTest);
    
37.                 System.out.println("After: " + Arrays.toString(toTest3) + "\n");
    
38.         }
    
39. }
    

复制代码

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

用的这个code

1. package Sorting;
   
2. 
   
3. public class QuickSortTest {
   
4. 
   
5.         public void qsort(int[] a){
   
6.                 qsort(a, 0, a.length - 1);
   
7.         }
   
8.        
   
9.         private void qsort(int[] a, int start, int end) {   
   
10.                    if (end <= start) return; // 其实这句可有可无, 只要调用的时候不故意出错
    
11.                   
    
12.                    int left = start;
    
13.                    int right = end;
    
14.                    //int pivot = a[left + (right - left) / 2];
    
15.                    int pivot = a[(left + right) / 2];
    
16. 
    
17.                    // selection
    
18.                    while (left <= right) {
    
19.                        while (a[left] < pivot) left ++;
    
20.                        while (a[right] > pivot) right --;
    
21.                        if (left <= right) {
    
22.                          int tmp = a[left];
    
23.                          a[left] = a[right];
    
24.                          a[right] = tmp;
    
25.                          left ++;
    
26.                          right --;
    
27.                        }
    
28.                    }
    
29.                   
    
30.                    // divide
    
31.                    if (left < end) qsort(a, left, end);
    
32.                    if (right > start) qsort(a, start, right);
    
33.                 }
    
34. 
    
35. }
    

复制代码

austurela 发表于 2013-11-18 13:59
Before: [5, 57, 51, 9, 75, 3, 65, 50, 86, 63]
After: [3, 5, 9, 50, 51, 57, 63, 65, 75, 86]

    int a = Integer.MAX_VALUE - 10;
    int b = Integer.MAX_VALUE - 1;
    int c;
   
    c = (a + b) / 2;
    System.out.println(c);
    c = a + (b - a) / 2;
    System.out.println(c);
    c = (a + b) >>> 1;
    System.out.println(c);

run this code