由于上一节学习了STL的使用，特别学习了vector的学习，所以在这里需要去回顾练习一下。下面是我的代码，我是用vector容器，实现了冒泡排序，选择排序和快速排序。特别的，在最后着重学习一个快速排序的原理。

（一）：vector练习，实现几个排序算法

//================================// Name        : VectorTest.cpp// Author      : hongboChen// Version     :// Copyright   : Your copyright notice// Description : 由于上一节学习使用了vector,//   所以现在练习使用一下vector的使用//   实现了几个排序的算法//===============================#include 
     
      #include 
      
       using namespace std;void swap(int &a,int &b);vector
       
          bubbleSort(vector
        
          vec);vector
         
           selectSort(vector
          
            vec);void quickSort(vector
           
             &vec,int first_lc,int last_lc);int main() { //用于保存vector的大小 int size = 0; cout << "Please enter the number of the array: "; cin >> size; //新建一个vector对象,并设置其大小 vector
            
              vec(size); //获取vector的遍历器 //vector
             
              ::iterator it = vec.begin(); //获取用户输入的数值,并赋值给vector cout << "Please enter the value of the array:" <
              
               > vec[i]; //或者是 //cin >> vec.at(i); //或者是 //it += i; //cin >> *it; } //下面就是对数组进行排序 //冒泡排序 //vec = bubbleSort(vec); //选择排序 //vec = selectSort(vec); //快速排序 quickSort(vec,0,size-1); for(int i = 0;i < size;i++){ cout << vec[i] << " "; } cout << endl; return 0;}//最简单的就是冒泡排序/** * 冒泡排序的思想就是 * 每次循环的时候都是找相邻的两个元素 * 如果相邻的两个元素符合顺序要求,就i不必切换位置 * 如果相邻的两个元素不符合顺序要求,就将这两个元素的位置对换 */vector
               
                 bubbleSort(vector
                
                  vec){ int size = vec.size(); //防止数组越界发生错误 for(int i = 0;i < size-1;i++){ for(int j = i;j < size-1;j++){ if(vec[j] > vec[j+1]) swap(vec[j],vec[j+1]); //进行交换 } } return vec;}/** * 下面是选择排序 * 选择排序的算法思想是: * 首先从所有的元素中选出最大的一个元素放在数组最后 * 接着从剩下的元素中再选出最大的一个元素放在后面 * 以此类推,就可以排出顺序 */vector
                 
                   selectSort(vector
                  
                    vec){ //用于保存选出的元素应该放到哪一个位置当中 int k = vec.size()-1; for(int i = 0;i < vec.size();i++){ int max_lc = 0; for(int j = 0;j <= k;j++){ if(vec[j] > vec[max_lc]) max_lc = j; } swap(vec[k],vec[max_lc]); k--; } return vec;}/** * 快速排序思想:算法复杂度为O(nlog(n)) * * 1:从数组中选出一个元素,通常情况下是选择第一个元素,称为"基准" * 2:将所有的比"基准"小的元素放在基准左边,比"基准大的元素"放在基准右边 * 3:采用递归,排序完成 *//** * vec : 要排序的数组 * first_lc : 第一个元素的位置 * last_lc : 最后一个元素的位置 * */void quickSort(vector
                   
                     &vec,int first_lc,int last_lc){ if(first_lc >= last_lc) return; int i = first_lc; int j = last_lc; int key = vec[first_lc]; while(i < j){ while(i < j && vec[j] > key) j--; vec[i] = vec[j]; while(i < j && vec[i] < key) i++; vec[j] = vec[i]; } vec[i] = key; quickSort(vec,0,i-1); quickSort(vec,i+1,last_lc);}/** * 先设定一个交换函数 */void swap(int &a,int &b){ int temp = a; a = b; b = temp;}
                   
                  
                 
                
               
              
             
            
           
          
         
        
       
      
     

（二）：快速排序的原理

首先，快速排序采用的是分而治之的思想，在快速排序中，有三步：

1:从数组中选出一个元素,通常情况下是选择第一个元素,称为”基准”

2:将所有的比”基准”小的元素放在基准左边,比”基准大的元素”放在基准右边

3:采用递归,排序完成

下面结合一个例子去理解一下。

下面是一个数组：

1：我们需要定义两个数值：

int i = 0; //第一个元素的位置

int j = 5; //最后一个元素的位置

同时我们还需要一个变量来表示我们选择的基准值（也就是第一个元素值）：

int key = array[i];

2：由于第一个元素即基准值被key取走了，所以我们需要找一个元素来取代这个位置，

我们刚刚看到，需要将小于基准值得元素放在其左边，所以，我们就需要从右向左找，

直到找到第一个小于基准值的元素，在这个例子中，在这个例子中，从右向左找一个小于

4的元素，在寻找过程中，j不断的在减小。

我们可以看到，当j=5 的时候，3 < 4的，所以此时

i = 0;

j = 5;

key = 4;

将位置5初的元素值替换位置0处的元素值。

3：此时，位置5处的数值3被空出来了，同理，由于需要将大于基准值得元素放在右边，所以我们需要

从左向右找到第一个大于4的值，就是6，此时

i = 2;

j = 5;

key = 4

进行替换：

4：此时，位置2处的6被空出来了，我们再从j位置开始，从右向左寻找第一个一个小于基准值的元素，

那就是1；

此时:

i = 2;

j = 4;

key = 4;

进行替换

5：我们接着再从i位置开始从左向右寻找第一个大于4的元素，就是7，则此时

i = 3;

j = 4;

key = 4;

进行替换：

当再继续进行的时候，从右向左再也找不到比4大的元素了，同时，从左向右再也找不到比4小的元素了，

所以，暂停一下，将基准值赋值给i所在位置的元素，即

array[i] = key;

则由此，比4小的都在4的左边了，比4大的都在4的右面了。

这样，将4的左边分离出来，4的右边分离出来，再进行上面同理的操作，最后就完成排序了。