Graphical explanation of how to implement quickSort quick sorting algorithm in Java

Compared with algorithms such as bubble sorting and selection sorting, the specific algorithm principle and implementation of quick sorting are somewhat difficult. In order to better understand quick sort, we still describe the algorithm principle of quick sort in detail in the form of examples. In the previous sorting algorithm, we took the height sorting problem of 5 athletes as an example to explain. In order to better reflect the characteristics of quick sorting, here we add 3 additional athletes. The details of the eight athletes in the example and their height information are as follows (F, G, and H are new athletes): A(181), B(169), C(187), D(172), E(163), F(191), G(189), H(182)

In the previous sorting algorithm, these sortings were all completed by the coach. Now that the number of athletes has increased, the coach also wants to take the opportunity to take a rest. , so the coach called two assistants and asked them to sort the heights of the eight athletes from left to right and from low to high using the quick sort method.

According to the algorithm principle of quick sorting method, two assistants stand on both sides of the athlete arrangement, as shown in the figure below

First, Assistant 1 starts from Select an athlete from the arrangement (usually the first athlete on the left or the middlemost athlete), here select athlete A (181). Since the sorting is from left to right and from low to high, Assistant 1 needs an athlete whose height is smaller than A(181) (the selected A(181)) as the benchmark for comparison. All comparisons in this round are with Initially selected athlete A (181) comparison):

# Let’s continue to refer to the detailed diagram of the first round of quick sorting.

/**
 * 对指定的数组中索引从start到end之间的元素进行快速排序
 * 
 * @param array 指定的数组
 * @param start 需要快速排序的数组索引起点
 * @param end 需要快速排序的数组索引终点
 */
public static final void quickSort(int[] array, int start, int end) {
  // i相当于助手1的位置，j相当于助手2的位置
  int i = start, j = end;
  int pivot = array[i]; // 取第1个元素为基准元素
  int emptyIndex = i; // 表示空位的位置索引，默认为被取出的基准元素的位置
  // 如果需要排序的元素个数不止1个，就进入快速排序(只要i和j不同，就表明至少有2个数组元素需要排序)
  while (i < j) {
    // 助手2开始从右向左一个个地查找小于基准元素的元素
    while (i < j && pivot <= array[j])
      j--;
    if (i < j) {
      // 如果助手2在遇到助手1之前就找到了对应的元素，就将该元素给助手1的"空位"，j成了空位
      array[emptyIndex] = array[emptyIndex = j];
    }
     
    // 助手1开始从左向右一个个地查找大于基准元素的元素
    while (i < j && array[i] <= pivot)
      i++;
    if (i < j) {
      // 如果助手1在遇到助手2之前就找到了对应的元素，就将该元素给助手2的"空位"，i成了空位
      array[emptyIndex] = array[emptyIndex = i];
    }
  }    
  // 助手1和助手2相遇后会停止循环，将最初取出的基准值给最后的空位
  array[emptyIndex] = pivot;
   
  // =====本轮快速排序完成=====
   
  // 如果分割点i左侧有2个以上的元素，递归调用继续对其进行快速排序
  if (i - start > 1) {
    quickSort(array, 0, i - 1);
  }
  // 如果分割点j右侧有2个以上的元素，递归调用继续对其进行快速排序
  if (end - j > 1) {
    quickSort(array, j + 1, end);
  }
}
 
//主方法
public static void main(String[] args) {
  // =====使用快速排序法对表示8名运动员身高的数组heights进行从低到高的排序=====
  // A(181)、B(169)、C(187)、D(172)、E(163)、F(191)、G(189)、H(182)
  int[] heights = { 181, 169, 187, 172, 163, 191, 189, 182 };
  // 调用快速排序方法
  quickSort(heights, 0, heights.length - 1);
  // 输出排序后的结果
  for (int height : heights) {
    System.out.println(height);
  }
}

163
169
172
181
182
187
189
191

There is another version of one-way scanning for quick sorting array splitting. The specific steps are to select the last element in the array as the splitting element, and set the same Two pointers, pointer i points to the position before the first element in the array, and pointer j points to the first element in the array. j scans from front to right, left to right, and increases i by one when it encounters an element that is less than or equal to the split element, and then swaps the elements pointed to by i and j. Finally, swap the element at position i+1 with the split element to complete an array division. The code is implemented as follows:

int partition(int[] a, int lo, int hi) {
  int i = lo - 1, j = lo;
  int v = a[hi];
  while (j < hi) {
    if (a[j] <= v) {
      swap(a, ++i, j);
    }
    j++;
  }
  swap(a, i + 1, hi);
  return i + 1;
}