Quick Sort

看一万遍忘一万遍，
再看亦是如初见。

对quick sort的思考，希望下次再看的时候能有蓦然回首灯火阑珊的感受！

对于quick sort, 无论排大排小，最核心的部分在于如何找到pivot, 并且为pivot 找到它最正确的位置。在业界，也叫用pivot 对需要排序的list进行partition.


  • 什么是partition?

简单说来，用K 对一个list进行partition，就是将该list分为两部分，一部分是小于k的部分，而另一部分是大于k的部分，然后输出那条分界线。

然而在quick sort中，在最核心的partition 之前，又多了一步，找pivot


  • 什么是pivot?

pivot就是一个list中的任意值，它可以将list分解为大于等于，和小于它的两部分，它所处的index就是该list此刻的值域分界线。
pivot可以是任意值，它的取值习惯一般分为种

    • start
    • end
    • mid
    • any
其中，最简单的取值方式要属于前面第一种和第二种，即start和end. 这是为什么呢？
因为在quick sort的时候，我们需要明确的知道每一条分界线具体的Index, 也就是说，在partition完成之后的那条分界限上的值必须要是之前选取的pivot.
简单说来，我们需要在记住pivot的位置，然后在partition结束后将pivot放置在那条分界线上。


  • 为什么要将每次选取的pivot放置在patition的分界线上？
我认为这是quick sort的精髓所在，在quick sort中，每次sort之后唯一确定的位置就是pivot的位置。因为pivot的位置固定，我们就可以使用divide and conquer 的算法，当找到该pivot的固定位置之后就可以只对（start, pivot-1） 和 （pivot+1, end）的部分进行sort.

Comments

Post a Comment

Popular posts from this blog

Sudoku

/*** Sudoku Given a partially filled 9×9 2D array ‘grid[9][9]‘, the goal is to assign digits (from 1 to 9) to the empty cells so that every row,   column, and subgrid of size 3×3 contains exactly one instance of the digits from 1 to 9. Backtracking Algorithm Like all other Backtracking problems, we can solve Sudoku by one by one assigning numbers to empty cells.  Before assigning a number, we check whether it is safe to assign. We basically check that the same number  is not present in current row, current column and current 3X3 subgrid. After checking for safety,  we assign the number, and recursively check whether this assignment leads to a solution or not.  If the assignment doesn’t lead to a solution, then we try next number for current empty cell.  And if none of number (1 to 9) lead to solution, we return false. ***/ #include <iostream> using namespace std; class Sudoku { public :      ...
Read more

Longest prefix matching - trie

/*** Longest prefix matching Given a dictionary of words and an input string, find the longest prefix of the string which is also a word in dictionary. Example: Let the dictionary contains the following words: {are, area, base, cat, cater, children, basement} Below are some input/output examples: -------------------------------------- Input String            Output -------------------------------------- caterer                 cater basemexy                base child                   < Empty > ***/ #include <iostream> #include <string> using namespace std; struct node {        char val; ...
Read more

Climbing Stairs

You are climbing a stair case. It takes  n  steps to reach to the top. Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top? Note:  Given  n  will be a positive integer. class Solution { public:     int climbStairs(int n) {         if (n == 0) return 0;                  if (n == 1) return 1;                  // dp space complexity is O(n)         vector<int> dp(n);         dp[0] = 1;         dp[1] = 2;                  for(int i = 2; i<n; i++)         {             dp[i] = dp[i-1] + dp[i-2];         }                  return dp[ n-1 ]...
Read more