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.

##When the two assistants were sorting and looking for After meeting during the process, the comparison of the current round is stopped, and the initially selected athlete A (181) is placed in the empty space where the two assistants meet

In quick sorting, when the two assistants meet , this round of sorting is over. At this time, we find that taking the position A(181) where the two athletes meet as the dividing point, those on the left side of the arrangement are all athletes with a height smaller than A(181), and those on the right side of the arrangement are all athletes with a height greater than A(181) athlete. At this time, we will look at the two sortings on the left and right sides of A(181) separately. If we continue to use the sorting methods of the two assistants mentioned above to sort the arrangements on both sides, then after multiple arrangements, finally We can get the sorting results we need.

The above is the entire sorting implementation process of quick sort. Quick sort uses the above sorting rules to divide one arrangement into two arrangements, and two arrangements into four arrangements, until there are no arrangements to separate, and finally we get the sorting result we need.

Now, we still program Java code to use quick sort to sort the heights of the above 8 athletes:

/**
 * 对指定的数组中索引从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);
  }
}

The output of the above Java code is as follows:

163
169
172
181
182
187
189
191

Note: Due to local differences in thinking, the code implementation of the above quick sort may have multiple variations. However, no matter what form of variation, the core idea of ​​quick sort does not change.

Another implementation: one-way scanning

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;
}

For more pictures and texts explaining the method of implementing the quickSort quick sorting algorithm in Java, please pay attention to the PHP Chinese website for related articles!