Ming
0%

排序算法

Posted on Edited on In

排序算法.png

比较类

交换类

bubbleSort

梦开始的地方

  • Java
1
2
3
4
5
6
7
8
9
public void bubbleSort(int[] nums) {
      for (int i = 0; i < nums.length; i++) {
          for (int j = 1; j < nums.length - i - 1; j++) {
              if (nums[j] < nums[j - 1]) {
                  swap(nums, j, j - 1);
              }
          }
      }
  }
  • Go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
func bucketSort(nums []int) {
   buckets := make([][]int, 10)

   for _, v := range nums {
      buckets[v/10] = append(buckets[v/10], v)
   }

   index := 0
   for i := range buckets {
      sort.Ints(buckets[i])
      for _, v := range buckets[i] {
         nums[index] = v
         index++
      }
   }
}

quickSort

我写的两个版本具体实现上稍微有些差别，但整体思路并无区别

  • Java
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
public void quickSort(int[] nums) {
    quickSort(nums, 0, nums.length - 1);
}

private void quickSort(int[] nums, int start, int end) {
    if (start >= end) {
        return;
    }
    int pivot = partition(nums, start, end);
    quickSort(nums, start, pivot);
    quickSort(nums, pivot + 1, end);
}

private int partition(int[] nums, int start, int end) {
    int pivot = start++;
    boolean flag = false;
    while (start <= end) {
        if (flag) {
            if (nums[pivot] < nums[start]) {
                swap(nums, pivot, start);
                flag = false;
                pivot = start;
            }
            start++;
        } else {
            if (nums[pivot] > nums[end]) {
                swap(nums, pivot, end);
                flag = true;
                pivot = end;
            }
            end--;
        }
    }
    return pivot;
}

  • Go

    Go虽然没有overload，但切片使得Go的快排更胜一筹

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// 美如画的快排
func quickSort(nums []int) {
   if len(nums) < 2 {
      return
   }

   left, right := 0, len(nums)-1
   pivot := nums[right]

   for i := range nums {
      if nums[i] < pivot {
         nums[i], nums[left] = nums[left], nums[i]
         left++
      }
   }
   nums[left], nums[right] = nums[right], nums[left]

   quickSort(nums[:left])
   quickSort(nums[left+1:])
}

插入类

insertionSort

  • Java
1
2
3
4
5
6
7
8
9
10
11
public void insertionSort(int[] nums) {
    for (int i = 1; i < nums.length; i++) {
        for (int j = i; j > 0; j--) {
            if (nums[j] < nums[j - 1]) {
                swap(nums, j, j - 1);
            } else {
                break;
            }
        }
    }
}
  • Go
1
2
3
4
5
6
7
8
9
10
11
func insertionSort(nums []int) {
   for i := 1; i < len(nums); i++ {
      for j := i; j > 0; j-- {
         if nums[j] < nums[j-1] {
            nums[j-1], nums[j] = nums[j], nums[j-1]
         } else {
            break
         }
      }
   }
}

shellSort

ShellSort is mainly a variation of Insertion Sort. In insertion sort, we move elements only one position ahead. When an element has to be moved far ahead, many movements are involved. The idea of shellSort is to allow exchange of far items.

  • Java
1
2
3
4
5
6
7
8
9
10
11
public void shellSort(int[] nums) {
    for (int step = nums.length / 2; step > 0; step /= 2) {
        for (int i = step; i < nums.length; i++) {
            for (int j = i; j - step >= 0; j -= step) {
                if (nums[j] < nums[j - step]) {
                    swap(nums, j, j - step);
                }
            }
        }
    }
}
  • Go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
// 希尔排序（Shell sort），也称递减增量排序算法，是插入排序的一种更高效的改进版本。希尔排序是非稳定排序算法
func shellSort(nums []int) {
   for step := len(nums) / 2; step > 0; step /= 2 {
      for i := step; i < len(nums); i++ {
         for j := i; j-step >= 0; j -= step {
            if nums[j] < nums[j-step] {
               nums[j], nums[j-step] = nums[j-step], nums[j]
            } else {
               break
            }
         }
      }
   }
}

选择类

selectionSort

  • Java
1
2
3
4
5
6
7
8
9
10
11
public void selectionSort(int[] nums) {
    for (int i = 0; i < nums.length; i++) {
        int min = nums[i];
        for (int j = i + 1; j < nums.length; j++) {
            if (nums[j] < min) {
                min = nums[j];
                swap(nums, i, j);
            }
        }
    }
}

heapSort

A complete binary tree is a binary tree in which every level, except possibly the last, is completely filled, and all nodes are as far left as possible

A Binary Heap is a Complete Binary Tree where items are stored in a special order such that value in a parent node is greater(or smaller) than the values in its two children nodes. The former is called as max heap and the latter is called min-heap. The heap can be represented by a binary tree or array.

Heap Sort Algorithm for sorting in increasing order:
1. Build a max heap from the input data.
2. At this point, the largest item is stored at the root of the heap. Replace it with the last item of the heap followed by reducing the size of heap by 1. Finally, heapify the root of the tree.
3. Repeat step 2 while size of heap is greater than 1.

  • Java
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) {
    for (int i = (nums.length / 2) - 1; i >= 0; i--) {
        sink(nums, i, nums.length);
    }
    int last = nums.length - 1;
    while (last > 0) {
        swap(nums, 0, last);
        last--;
        sink(nums, 0, last + 1);
    }
}

private void sink(int[] nums, int rootIndex, int length) {
    // 如果该节点有两颗子树
    if (rootIndex * 2 + 2 <= length - 1) {
        int left = rootIndex * 2 + 1;
        int right = left + 1;
        if (nums[rootIndex] > Math.max(nums[left], nums[right])) {
            return;
        }
        if (nums[left] < nums[right]) {
            swap(nums, rootIndex, right);
            sink(nums, right, length);
        } else {
            swap(nums, rootIndex, left);
            sink(nums, left, length);
        }
        return;
    }
    // 如果只有左子树
    if (rootIndex * 2 + 1 <= length - 1) {
        int left = rootIndex * 2 + 1;
        if (nums[rootIndex] < nums[left]) {
            swap(nums, rootIndex, left);
        }
    }
}
  • Go
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
// 美如画的堆排序
func headSort(nums []int) {
   // build max-heap
   for i := len(nums)/2 - 1; i >= 0; i-- {
      sink(nums, len(nums), i)
   }

   // extract element from heap
   for i := len(nums) - 1; i > 0; i-- {
      nums[0], nums[i] = nums[i], nums[0]
      sink(nums, i, 0)
   }
}

func sink(nums []int, size, index int) {
	maxIdx := index
	left, right := 2*index+1, 2*index+2
	if left < size && nums[left] > nums[maxIdx] {
		maxIdx = left
	}
	if right < size && nums[right] > nums[maxIdx] {
		maxIdx = right
	}
	if maxIdx != index {
		nums[maxIdx], nums[index] = nums[index], nums[maxIdx]
		// now nums[maxIdx] is the smallest one of the three
		sink(nums, size, maxIdx)
	}
}

归并类

mergeSort

  • Java
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
public void mergeSort(int[] nums) {
    mergeSort(nums, 0, nums.length - 1, new int[nums.length]);
}

private void mergeSort(int[] nums, int start, int end, int[] tmp) {
    if (start >= end) {
        return;
    }
    int mid = (start + end) / 2;
    mergeSort(nums, start, mid, tmp);
    mergeSort(nums, mid + 1, end, tmp);
    merge(nums, start, mid, mid + 1, end, tmp);
}

private void merge(int[] nums, int left1, int right1, int left2, int right2, int[] tmp) {
    int start = left1;
    int index = left1;
    while (left1 <= right1 && left2 <= right2) {
        if (nums[left1] <= nums[left2]) {
            tmp[index] = nums[left1++];
        } else {
            tmp[index] = nums[left2++];
        }
        index++;
    }
    for (int i = left1; i <= right1; i++) {
        tmp[index++] = nums[i];
    }
    for (int i = left2; i <= right2; i++) {
        tmp[index++] = nums[i];
    }
    System.arraycopy(tmp, start, nums, start, right2 + 1 - start);
}
  • Go

切片被玩穿了啊

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
38
// 有点丑陋的归并排序
func mergeSort(nums []int) {
   n := len(nums)
   if n == 1 {
      return
   }

   mid := n / 2
   left, right := make([]int, mid), make([]int, n-mid)
   copy(left, nums[:mid])
   copy(right, nums[mid:])

   mergeSort(left)
   mergeSort(right)
   merge(left, right, nums)
}

func merge(left, right, res []int) {
   var i int
   for i = 0; len(left) > 0 && len(right) > 0; i++ {
      if left[0] < right[0] {
         res[i] = left[0]
         left = left[1:]
      } else {
         res[i] = right[0]
         right = right[1:]
      }
   }

   for _, v := range left {
      res[i] = v
      i++
   }
   for _, v := range right {
      res[i] = v
      i++
   }
}

  • 复杂度

    时间复杂度：O（nlogn）

    空间复杂度：O（n），非原地排序

非比较类

countingSort

  • Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
public void countingSort(int[] nums) {
    var max = Arrays.stream(nums).max().getAsInt();
    var min = Arrays.stream(nums).min().getAsInt();
    int[] cnt = new int[max - min + 1];
    for (int num : nums) {
        cnt[num - min]++;
    }
    int index = 0;
    for (int i = 0; i < cnt.length; i++) {
        for (int j = 0; j < cnt[i]; j++) {
            nums[index++] = i + min;
        }
    }
}

  • Go

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    func countingSort(nums []int) {
       var min, max int
       for i, v := range nums {
          if i == 0 || min > v {
             min = v
          }
          if i == 0 || max < v {
             max = v
          }
       }

       cnt := make([]int, max-min+1)
       for _, v := range nums {
          cnt[v-min]++
       }

       index := 0
       for i, v := range cnt {
          for j := 0; j < v; j++ {
             nums[index] = i + min
             index++
          }
       }
    }

bucketSort

  • Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public void bucketSort(int[] nums) {
    List<List<Integer>> buckets = new ArrayList<>();
    for (int i = 0; i < 10; i++) {
        buckets.add(new ArrayList<>());
    }
    for (int num : nums) {
        buckets.get(num / 10).add(num);
    }
    int index = 0;
    for (var bucket : buckets) {
        bucket.sort(Integer::compare);
        for (int num : bucket) {
            nums[index++] = num;
        }
    }
}

  • Go

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    func bucketSort(nums []int) {
       buckets := make([][]int, 10)

       for _, v := range nums {
          buckets[v/10] = append(buckets[v/10], v)
       }

       index := 0
       for i := range buckets {
          sort.Ints(buckets[i])
          for _, v := range buckets[i] {
             nums[index] = v
             index++
          }
       }
    }

radixSort

  • Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public void radixSort(int[] nums) {
    List<List<Integer>> buckets = new ArrayList<>();
    for (int i = 0; i < 10; i++) {
        buckets.add(new ArrayList<>());
    }
    int div = 1, mod = 10;
    int length = Integer.toString(Arrays.stream(nums).max().getAsInt()).length();
    for (int i = 0; i < length; i++) {
        for (int num : nums) {
            buckets.get(num % mod / div).add(num);
        }
        div *= 10;
        mod *= 10;
        int index = 0;
        for (var bucket : buckets) {
            for (int num : bucket) {
                nums[index++] = num;
            }
            bucket.clear();
        }
    }
}
  • Go
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
func radixSort(nums []int) {
   // how many digits does the max num has?
   var max int
   for i, v := range nums {
      if i == 0 || max < v {
         max = v
      }
   }
   maxLen := len(strconv.Itoa(max))

   div, mod := 1, 10
   for i := 0; i < maxLen; i++ {
      buckets := make([][]int, 10)
      for _, v := range nums {
         buckets[v%mod/div] = append(buckets[v%mod/div], v)
      }
      div *= 10
      mod *= 10

      index := 0
      for _, bucket := range buckets {
         for _, num := range bucket {
            nums[index] = num
            index++
         }
      }
   }
}

Assemble

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public class Main {
    public static void main(String[] args) {
        var sort = new Sort();
        var nums = sort.randomArray();
        System.out.println(Arrays.toString(nums));
//        sort.bubbleSort(nums);
//        sort.selectionSort(nums);
//        sort.insertionSort(nums);
//        sort.shellSort(nums);
//        sort.mergeSort(nums);
//        sort.quickSort(nums);
//        sort.heapSort(nums);
//        sort.countingSort(nums);
//        sort.bucketSort(nums);
//        sort.radixSort(nums);
        System.out.println(Arrays.toString(nums));
    }
}
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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
class Sort {
    public void bubbleSort(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            for (int j = 1; j < nums.length - i - 1; j++) {
                if (nums[j] < nums[j - 1]) {
                    swap(nums, j, j - 1);
                }
            }
        }
    }

    public void selectionSort(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            int min = nums[i];
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[j] < min) {
                    min = nums[j];
                    swap(nums, i, j);
                }
            }
        }
    }

    public void insertionSort(int[] nums) {
        for (int i = 1; i < nums.length; i++) {
            for (int j = i; j > 0; j--) {
                if (nums[j] < nums[j - 1]) {
                    swap(nums, j, j - 1);
                } else {
                    break;
                }
            }
        }
    }

    public void shellSort(int[] nums) {
        for (int step = nums.length / 2; step > 0; step /= 2) {
            for (int i = step; i < nums.length; i++) {
                for (int j = i; j - step >= 0; j -= step) {
                    if (nums[j] < nums[j - step]) {
                        swap(nums, j, j - step);
                    }
                }
            }
        }
    }

    ////////////////////////////////////////////////////////

    public void mergeSort(int[] nums) {
        mergeSort(nums, 0, nums.length - 1, new int[nums.length]);
    }

    private void mergeSort(int[] nums, int start, int end, int[] tmp) {
        if (start >= end) {
            return;
        }
        int mid = (start + end) / 2;
        mergeSort(nums, start, mid, tmp);
        mergeSort(nums, mid + 1, end, tmp);
        merge(nums, start, mid, mid + 1, end, tmp);
    }

    private void merge(int[] nums, int left1, int right1, int left2, int right2, int[] tmp) {
        int start = left1;
        int index = left1;
        while (left1 <= right1 && left2 <= right2) {
            if (nums[left1] <= nums[left2]) {
                tmp[index] = nums[left1++];
            } else {
                tmp[index] = nums[left2++];
            }
            index++;
        }
        for (int i = left1; i <= right1; i++) {
            tmp[index++] = nums[i];
        }
        for (int i = left2; i <= right2; i++) {
            tmp[index++] = nums[i];
        }
        System.arraycopy(tmp, start, nums, start, right2 + 1 - start);
    }

    ////////////////////////////////////////////////////////

    public void quickSort(int[] nums) {
        quickSort(nums, 0, nums.length - 1);
    }

    private void quickSort(int[] nums, int start, int end) {
        if (start >= end) {
            return;
        }
        int pivot = partition(nums, start, end);
        quickSort(nums, start, pivot);
        quickSort(nums, pivot + 1, end);
    }

    private int partition(int[] nums, int start, int end) {
        int pivot = start++;
        boolean flag = false;
        while (start <= end) {
            if (flag) {
                if (nums[pivot] < nums[start]) {
                    swap(nums, pivot, start);
                    flag = false;
                    pivot = start;
                }
                start++;
            } else {
                if (nums[pivot] > nums[end]) {
                    swap(nums, pivot, end);
                    flag = true;
                    pivot = end;
                }
                end--;
            }
        }
        return pivot;
    }

    ////////////////////////////////////////////////////////

    public void heapSort(int[] nums) {
        for (int i = (nums.length / 2) - 1; i >= 0; i--) {
            sink(nums, i, nums.length);
        }
        int last = nums.length - 1;
        while (last > 0) {
            swap(nums, 0, last);
            last--;
            sink(nums, 0, last + 1);
        }
    }

    private void sink(int[] nums, int rootIndex, int length) {
        // 如果该节点有两颗子树
        if (rootIndex * 2 + 2 <= length - 1) {
            int left = rootIndex * 2 + 1;
            int right = left + 1;
            if (nums[rootIndex] > Math.max(nums[left], nums[right])) {
                return;
            }
            if (nums[left] < nums[right]) {
                swap(nums, rootIndex, right);
                sink(nums, right, length);
            } else {
                swap(nums, rootIndex, left);
                sink(nums, left, length);
            }
            return;
        }
        // 如果只有左子树
        if (rootIndex * 2 + 1 <= length - 1) {
            int left = rootIndex * 2 + 1;
            if (nums[rootIndex] < nums[left]) {
                swap(nums, rootIndex, left);
            }
        }
    }

    ////////////////////////////////////////////////////////

    public void countingSort(int[] nums) {
        var max = Arrays.stream(nums).max().getAsInt();
        var min = Arrays.stream(nums).min().getAsInt();
        int[] cnt = new int[max - min + 1];
        for (int num : nums) {
            cnt[num - min]++;
        }
        int index = 0;
        for (int i = 0; i < cnt.length; i++) {
            for (int j = 0; j < cnt[i]; j++) {
                nums[index++] = i + min;
            }
        }
    }

    public void bucketSort(int[] nums) {
        List<List<Integer>> buckets = new ArrayList<>();
        for (int i = 0; i < 10; i++) {
            buckets.add(new ArrayList<>());
        }
        for (int num : nums) {
            buckets.get(num / 10).add(num);
        }
        int index = 0;
        for (var bucket : buckets) {
            bucket.sort(Integer::compare);
            for (int num : bucket) {
                nums[index++] = num;
            }
        }
    }

    public void radixSort(int[] nums) {
        List<List<Integer>> buckets = new ArrayList<>();
        for (int i = 0; i < 10; i++) {
            buckets.add(new ArrayList<>());
        }
        int div = 1, mod = 10;
        int length = Integer.toString(Arrays.stream(nums).max().getAsInt()).length();
        for (int i = 0; i < length; i++) {
            for (int num : nums) {
                buckets.get(num % mod / div).add(num);
            }
            div *= 10;
            mod *= 10;
            int index = 0;
            for (var bucket : buckets) {
                for (int num : bucket) {
                    nums[index++] = num;
                }
                bucket.clear();
            }
        }
    }

    private void swap(int[] nums, int index1, int index2) {
        int tmp = nums[index1];
        nums[index1] = nums[index2];
        nums[index2] = tmp;
    }

    public int[] randomArray() {
        int[] nums = new int[10];
        for (int i = 0; i < nums.length; i++) {
            nums[i] = (int) (Math.random() * 100);
        }
        return nums;
    }
}