Quicksort is a frequently used sorting algorithm with a time complexity of O(nlogn). Because it’s generally faster than other common sorting methods, it’s widely used, so I decided to try implementing it myself.

Principle#

Quicksort utilizes the principle of divide and conquer: Select a number from the array and divide the array into two parts. Using the selected number as a pivot, place elements smaller than the pivot to its left, and elements greater than the pivot to its right. This ensures that all elements to the left of the pivot are smaller than it, and all elements to its right are larger. Then, recursively repeat the process for the left and right subarrays of the pivot until each subarray has a length of 1. Finally, combining these separated arrays completes the process. The steps are as follows:

1. Randomly select an element from the array to serve as the pivot. Compare each element in the array with the pivot, placing those smaller than the pivot to its left, and those greater than the pivot to its right.
2. Repeat Step 1 for the left and right partitions created in the previous step.
3. Stop when all partitions have a length of 1.

Implementation#

Below are implementations in languages I’m familiar with (using the first element as the pivot and employing a recursive approach):

Python Version#

    def quick_sort(lst,left,right):
    	i = left;
    	j = right
    	if i >= j:
    		return lst
    	k = lst[i]
    	while i < j:
    		while i < j and lst[j] >= k:		#lst[j]<=k时，循环结束，并将其值赋给lst[i]
    			j -= 1
    		lst[i] = lst[j]
    		while i < j and lst[i] <= k:		#lst[i]>=k时，循环结束，并将其值赋给lst[j]
    			i += 1
    		lst[j] = lst[i]
    	lst[i] = k								#当i>=j时，将k的值赋给lst[i]
    	quick_sort(lst,left,i-1)
    	quick_sort(lst,j+1,right)
    	return lst

JavaScript Version#

function quick_sort(lst, l, r) {
  var i = l,
    j = r,
    k = lst[l];
  if (i >= j) {
    return lst;
  }
  while (i < j) {
    for (; i < j; j--) {
      if (lst[j] <= k) {
        lst[i] = lst[j];
        i++;
        break;
      }
    }
    for (; i < j; i++) {
      if (lst[i] >= k) {
        lst[j] = lst[i];
        j--;
        break;
      }
    }
  }
  lst[i] = k;
  quick_sort(lst, l, i - 1);
  quick_sort(lst, j + 1, r);
  return lst;
}

C Language Version#

    void qucik_sort(int lst[],int l,int r)
    {
    	if(l < r)
    	{
    		int i = l, j = r, k = lst[l];
    		while (i < j){
    			for (; i < j; --j)
    			{
    				if (lst[j] <= k)
    				{
    					lst[i] = lst [j];
    					i++;
    					break;
    				}
    			}
    			for (; i < j; ++i)
    			{
    				if (lst[i] >= k)
    				{
    					lst[j] = lst[i];
    					j--;
    					break;
    				}
    			}
    		}
    		lst[i] = k;
    		qucik_sort(lst, l, i-1);
    		qucik_sort(lst, j+1, r);
    	}
    }