Shulou(Shulou.com)06/01 Report--

This article is about how to implement a quick sort algorithm for static link libraries using class templates in Linux. Xiaobian thinks it is quite practical, so share it with everyone for reference. Let's follow Xiaobian and have a look.

The essence of quick sorting is to select a reference value ref from the array, place it on the right side of ref if it is larger than the reference value, and place it on the left side if it is smaller than ref, and then repeat the action on both sides.

Let's start with a quick list of steps:

1. Select a reference value ref from the array, and place it to the right of ref if it is larger than ref

The above action divides the array into two parts:

A ref B

A is the set of array elements smaller than ref, which is still an array, B is the set of elements larger than ref, which is still an array

2. Repeat the above actions for the elements on both sides of ref until there is only one element left in A and B, and the sorting is complete.

The point is how to select two sets A and B separately. In the Introduction to the Algorithm, this step is called the partition action.

First of all, the pseudo-code inside the algorithm introduction is posted out. Let's take a look at it first:

Let's look at the first selection method of ref, that is, ref = a[r]

partition(a[], p, r){i = pj = p-1ref = a[r]for(; i

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.