总结下各种排序算法

Sroting Algorithms

1. Selection Sort

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public void selectionSort(int[] nums) {
 for (int i = 0; i < nums.length; i++) {
        // Exchange a[i] with smallest entry in a[i+1...N).
        int min = i;
        for (int j = i + 1; j < nums.length; j++) {
            if (nums[j] < nums[min]) {
                min = j;
            }
        }
        int temp = nums[i];
        nums[i] = nums[min];
        nums[min] = temp;
    }
}

2. Bubble Sort

1
2
3
4
5
6
7
8
9
10
11
12
public void bubbleSort(int[] nums) {
	int n = nums.length;
    for (int i = 0; i < n; i++) {
        for (int j = 1; j < n - i; j++) {
            if (nums[j - 1] > nums[j]) {
                int temp = nums[j - 1];
                nums[j - 1] = nums[j];
                nums[j] = temp;
            }
        }
    }
}

3. Insertion Sort

1
2
3
4
5
6
7
8
9
10
public void insertionSort(int[] nums) {
 for (int i = 1; i < nums.length; i++) {
        // Insert a[i] among a[i-1], a[i-2], a[i-3]... ..
        for (int j = i; j > 0 && nums[j] < nums[j - 1]; j--) {
            int temp = nums[j];
            nums[j] = nums[j - 1];
            nums[j - 1] = temp;
        }
    }
}

4. ShellSort

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public void shellSort(int[] nums) {
   int n = nums.length;
    int h = 1;
    while (h < n / 3) {
        // 1, 4, 13, 40, 121, 364, 1093, ...
        h = 3 * h + 1;
    }
    // h-sort the array.
    while (h >= 1) {
        // Insert a[i] among a[i-h], a[i-2*h], a[i-3*h]... .
        for (int i = h; i < n; i++) {
            for (int j = i; j >= h && nums[j] < nums[j - h]; j -= h) {
                int temp = nums[j];
                nums[j] = nums[j - h];
                nums[j - h] = temp;
            }
        }
        h = h / 3;
    }
}

5. Quick Sort

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
private void quickSort(int[] A, int start, int end) {
    if (start >= end) {
        return;
    }
    int left = start, right = end;
    // key point 1: pivot is the value, not the index
    int pivot = A[(start + end) / 2];
    // key point 2: every time you compare left & right, it should be
    // left <= right not left < right
    while (left <= right) {
        // key point 3: A[left] < pivot not A[left] <= pivot
        while (left <= right && A[left] < pivot) {
            left++;
        }
        // key point 3: A[right] > pivot not A[right] >= pivot
        while (left <= right && A[right] > pivot) {
            right--;
        }
        if (left <= right) {
            int temp = A[left];
            A[left] = A[right];
            A[right] = temp;
            left++;
            right--;
        }
    }
    quickSort(A, start, right);
    quickSort(A, left, end);
}

6. Merge Sort

7. Heap Sort

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
public void heapSort(int[] nums) {
    buildMaxHeap(nums);
    int n = nums.length;
    for (int i = n - 1; i >= 1; i--) {
        exchange(nums, i, 0);
        maxHeapify(nums, 0, i);
    }
}
private void maxHeapify(int[] nums, int i, int max) {
    int l = 2 * i + 1;
    int r = 2 * i + 2;
    int largest = i;
    if (l < max && nums[l] > nums[i])
        largest = l;
    if (r < max && nums[r] > nums[largest])
        largest = r;
    if (largest != i) {
        exchange(nums, largest, i);
        maxHeapify(nums, largest, max);
    }
}
private void buildMaxHeap(int[] nums) {
    for (int i = nums.length / 2 - 1; i >= 0; i--) {
        maxHeapify(nums, i, nums.length);
    }
}
private void exchange(int[] nums, int i, int j) {
    int temp = nums[i];
    nums[i] = nums[j];
    nums[j] = temp;
}

8. Counting Sort

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// In place sorting
public void sortColors(int[] nums, int k) {
 if(nums == null || nums.length == 0)
        return;
    int[] counter = new int[k];
    for(int n : nums) {
        counter[n]++;
    }
    for(int i = 0, idx = 0; i < k; i++) {
        while(counter[i]-- > 0) {
            nums[idx++] = i;    
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
int[] countingSort(int[] a, int k) {
	int c[] = new int[k];
    for (int i = 0; i < a.length; i++)
        c[a[i]]++;
    for (int i = 1; i < k; i++)
        c[i] += c[i-1];
    int b[] = new int[a.length];
    for (int i = a.length-1; i >= 0; i--)
        b[--c[a[i]]] = a[i];
    return b;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public static int[] countSort(int[] a) {
    int b[] = new int[a.length];
    int max = a[0], min = a[0];
    for (int i : a) {
        if (i > max) {
            max = i;
        }
        if (i < min) {
            min = i;
        }
    }//这里k的大小是要排序的数组中，元素大小的极值差+1
    int k = max - min + 1;
    int c[] = new int[k];
    for (int i = 0; i < a.length; ++i) {
        c[a[i] - min] += 1;//优化过的地方，减小了数组c的大小
    }
    for (int i = 1; i < c.length; ++i) {
        c[i] = c[i] + c[i - 1];
    }
    for (int i = a.length - 1; i >= 0; --i) {
        b[--c[a[i] - min]] = a[i];//按存取的方式取出c的元素
    }
    return b;
}

9. Bucket Sort

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
public static int[] bucketSort(int[] array, int bucketCount) {
    if (bucketCount <= 0) throw new IllegalArgumentException("Invalid bucket count");
    if (array.length <= 1) return array; //trivially sorted
    int high = array[0];
    int low = array[0];
    for (int i = 1; i < array.length; i++) { //find the range of input elements
        if (array[i] > high) high = array[i];
        if (array[i] < low) low = array[i];
    }
    double interval = ((double)(high - low + 1))/bucketCount; //range of one bucket
    ArrayList<Integer> buckets[] = new ArrayList[bucketCount];
    for (int i = 0; i < bucketCount; i++) { //initialize buckets
        buckets[i] = new ArrayList();
    }
    for (int i = 0; i < array.length; i++) { //partition the input array
        buckets[(int)((array[i] - low)/interval)].add(array[i]);
    }
    int pointer = 0;
    for (int i = 0; i < buckets.length; i++) {
        Collections.sort(buckets[i]); //mergeSort
        for (int j = 0; j < buckets[i].size(); j++) { //merge the buckets
            array[pointer] = buckets[i].get(j);
            pointer++;
        }
    }
    return array;
}

10. Radix Sort

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int[] radixSort(int[] a) {
    int[] b = null;
    for (int p = 0; p < w/d; p++) {
        int c[] = new int[1<<d];
        // the next three for loops implement counting-sort
        b = new int[a.length];
        for (int i = 0; i < a.length; i++)
            c[(a[i] >> d*p)&((1<<d)-1)]++;
        for (int i = 1; i < 1<<d; i++)
            c[i] += c[i-1];
        for (int i = a.length-1; i >= 0; i--)
            b[--c[(a[i] >> d*p)&((1<<d)-1)]] = a[i];
        a = b;
    }
    return b;
}