STL vector練習

版權聲明：您好，轉載請留下本人部落格的位址，謝謝 https://blog.csdn.net/hongbochen1223/article/details/45116115

由于上一節學習了STL的使用，特别學習了vector的學習，是以在這裡需要去回顧練習一下。下面是我的代碼，我是用vector容器，實作了冒泡排序，選擇排序和快速排序。特别的，在最後着重學習一個快速排序的原理。

（一）：vector練習，實作幾個排序算法

//================================
// Name        : VectorTest.cpp
// Author      : hongboChen
// Version     :
// Copyright   : Your copyright notice
// Description : 由于上一節學習使用了vector,
//   是以現在練習使用一下vector的使用
//   實作了幾個排序的算法
//===============================

#include <iostream>
#include <vector>

using namespace std;

void swap(int &a,int &b);
vector<int>  bubbleSort(vector<int> vec);
vector<int> selectSort(vector<int> vec);
void quickSort(vector<int> &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<int> vec(size);

 //擷取vector的周遊器
 //vector<int>::iterator it = vec.begin();

 //擷取使用者輸入的數值,并指派給vector
 cout << "Please enter the value of the array:" <<endl;

 for(int i = 0; i < size;i++){
  cin >> 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<int>  bubbleSort(vector<int> 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<int> selectSort(vector<int> 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<int> &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;

key = 4

進行替換：

4：此時，位置2處的6被空出來了，我們再從j位置開始，從右向左尋找第一個一個小于基準值的元素，

那就是1；

此時:

j = 4;

進行替換

5：我們接着再從i位置開始從左向右尋找第一個大于4的元素，就是7，則此時

i = 3;

當再繼續進行的時候，從右向左再也找不到比4大的元素了，同時，從左向右再也找不到比4小的元素了，

是以，暫停一下，将基準值指派給i所在位置的元素，即

array[i] = key;

則由此，比4小的都在4的左邊了，比4大的都在4的右面了。

這樣，将4的左邊分離出來，4的右邊分離出來，再進行上面同理的操作，最後就完成排序了。