欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

C++中的幾種排序算法

 更新時(shí)間:2014年02月24日 15:27:01   作者:  
這篇文章主要介紹了C++中的幾種排序算法,需要的朋友可以參考下

SortAlgorithm.h

復(fù)制代碼 代碼如下:

#include <vector>
using namespace std;

class SortAlgorithm
{
public:
    SortAlgorithm(int = 10);
    void displayVector();
    void swap(int &, int &);

    void insertSort();                     //O(n^2)
    void selectSort();                    //O(n^2)
    void mergeSort();                    //O(n log n)
    void bubbleSort();                  //O(n^2)
    void quickSort(  int , int  );     //worst: O(n^2),  best: O(n log n)

    int partition( int , int  );
    void sortSubVector(int , int );
    void merge(int , int , int , int );
private:
    int size;
    vector< int > source;
    vector< int > temp;

};

SortAlgorithm.cpp

復(fù)制代碼 代碼如下:

#include <iostream>
#include <cstdlib> // prototypes for functions srand and rand
#include <ctime> // prototype for function time
#include <algorithm> // prototype for sort function
#include "SortAlgorithm.h" // class BinarySearch definition
using namespace std;

SortAlgorithm::SortAlgorithm(int vectorSize)
{
    size = ( vectorSize > 0 ? vectorSize : 10 ); // validate vectorSize
    srand( time( 0 ) ); // seed using current time

   // fill vector with random ints in range 10-99
    for ( int i = 0; i < size; i++ )
           source.push_back( 10 + rand() % 90 ); // 10-99

    temp = source;
}

void SortAlgorithm::insertSort()
{
    int insert;
    for(int next = 1; next < size; next++){
        insert = temp[next];
        int moveItem = next;

        while((moveItem > 0) && (temp[moveItem - 1] > insert)){
            temp[moveItem] = temp[moveItem - 1];
            moveItem--;
        }

        temp[moveItem] = insert;
    }
}

void SortAlgorithm::selectSort()
{
    int loop = size - 1;
    int smallest;

    for(int i = 0; i < loop; i++){
        smallest = i;

        for(int j = i + 1; j < size; j++){
            if(temp[j] < temp[smallest])
                smallest = j;
        }

        swap(temp[i], temp[smallest]);
    }
}

void SortAlgorithm::mergeSort()
{
    sortSubVector(0, size - 1);
}

void SortAlgorithm::bubbleSort()
{
       int comp; // used to control for loop and for subscripts
       bool swapCheck = true; // was a swap made?

    for ( int pass = 1; pass < size && swapCheck; pass++ ) {
        swapCheck = false; // assume no swaps will be made

      // traverse and compare unsorted part of vector
        for ( comp = 0; comp < size - pass; comp++ ){

         // compare adjacent vector elements
            if ( temp[ comp ] > temp[ comp + 1 ] ) {
                swap(temp[comp], temp[comp + 1]);
                swapCheck = true;
                 } // end if

        } // end inner for
    } // end outer for
}

void SortAlgorithm::quickSort(int first, int last )
{
   int currentLocation;

   if ( first >= last )
      return;

   currentLocation = partition( first, last ); // place an element
   quickSort( first, currentLocation - 1 ); // sort left side
   quickSort( currentLocation + 1, last ); // sort right side
} // end function quickSortHelper

// partition the vector into multiple sections
int SortAlgorithm::partition( int left, int right )
{
   int position = left;

   // loop through the portion of the vector
   while ( true )
   {
   //first: from right ro left
      while ( temp[ position ] <= temp[ right ] && position != right )
         --right;

      if ( position == right )
         return position;

      if ( temp[ position ] > temp[ right ])
      {
         swap( temp[ position ], temp[ right ] );
         position = right;
      } // end if
   //second: from left to right
      while ( temp[ left ] <= temp[ position ] && left != position )
         ++left;

      if ( position == left )
         return position;

      if ( temp[ left ] > temp[ position ] )
      {
         swap( temp[ position ], temp[ left ] );
         position = left;
      } // end if
   } // end while
} // end function partition

void SortAlgorithm::sortSubVector(int low, int high)
{
    if((high - low) >= 1){
        int middle1 = (low + high) / 2;
        int middle2 = middle1 + 1;

        /*cout << "split:   ";
        displaySubVector(low, high);
        cout << endl << "       ";
        displaySubVector(low, middle1);
        cout << endl << "       ";
        displaySubVector(middle2, high);
        cout << endl << endl;*/

        sortSubVector(low, middle1);
        //cout << "Stop here1. low = " << low << ", middle1 = " << middle1 << endl;
        sortSubVector(middle2, high);
        //cout << "Stop here2. middle2 = " << middle2 << ", high = " << high << endl;

        merge(low, middle1, middle2, high);

    }
}

void SortAlgorithm::merge(int left, int middle1, int middle2, int right)
{
    int leftIndex = left;
    int rightIndex = middle2;
    int combinedIndex = left;
    vector<int> combined(size);

    /*cout << "merge:   ";
    displaySubVector(left, middle1);
    cout << endl << "       ";
    displaySubVector(middle2, right);
    cout << endl;*/

    while(leftIndex <= middle1 && rightIndex <= right){
        if(temp[leftIndex] <= temp[rightIndex])
            combined[combinedIndex++] = temp[leftIndex++];
        else
            combined[combinedIndex++] = temp[rightIndex++];
    }

    if(leftIndex == middle2){
        while(rightIndex <= right)
            combined[combinedIndex++] = temp[rightIndex++];
    }
    else{
        while(leftIndex <= middle1)
            combined[combinedIndex++] = temp[leftIndex++];
    }

    for(int i = left; i <= right; i++)
        temp[i] = combined[i];

    /*cout << "       ";
    displaySubVector(left, right);
    cout << endl << endl;*/
}

void SortAlgorithm::swap(int &x, int &y)
{
    int t;

    t = x;
    x = y;
    y = t;
}

void SortAlgorithm::displayVector()
{
    for(int i = 0; i < size; i++){
        cout << " " << temp[i];
        if((i + 1) % 10 == 0)
            cout << endl;
    }

    cout << endl;

    temp = source;
}

main.cpp

復(fù)制代碼 代碼如下:

#include <iostream>
#include "SortAlgorithm.h" // class BinarySearch definition
#include "BucketSort.h"
using namespace std;

int main()
{
    int num;
    cout << "Please input the integer number you want to sort:  ";
    cin >> num;

    SortAlgorithm sortVector(num);
    cout << "Unsort elements: \n";
    sortVector.displayVector();

    sortVector.insertSort();
    cout << "\nInsert sorted elements: \n";
    sortVector.displayVector();

    sortVector.selectSort();
    cout << "\nSelect sorted elements: \n";
    sortVector.displayVector();

    sortVector.mergeSort();
    cout << "\nMerge sorted elements: \n";
    sortVector.displayVector();

    sortVector.bubbleSort();
    cout << "\nBubble sorted elements: \n";
    sortVector.displayVector();

    sortVector.quickSort(0, num - 1);
    cout << "\nQuick sorted elements: \n";
    sortVector.displayVector();

   /*BucketSort bucketSortVector( num ); // create BucketSort object

   cout << "Vector elements in original order:\n";
   bucketSortVector.displayElements();

   bucketSortVector.sort(); // sort the vector

   cout << "\nVector elements in sorted order:\n";
   bucketSortVector.displayElements();*/
}

相關(guān)文章

  • c語(yǔ)言常見(jiàn)圖片格式判斷實(shí)例

    c語(yǔ)言常見(jiàn)圖片格式判斷實(shí)例

    這篇文章介紹了c語(yǔ)言常見(jiàn)圖片格式判斷實(shí)例,有需要的朋友可以參考一下
    2013-09-09
  • QT實(shí)戰(zhàn)之實(shí)現(xiàn)圖片瀏覽系統(tǒng)

    QT實(shí)戰(zhàn)之實(shí)現(xiàn)圖片瀏覽系統(tǒng)

    這篇文章主要介紹了如何利用QT編寫一個(gè)圖片瀏覽系統(tǒng),可以支持自動(dòng)播放,左右拖動(dòng)切換,點(diǎn)擊列表切換,點(diǎn)擊按鈕切換等功能,感興趣的小伙伴可以跟隨小編一起了解一下
    2023-04-04
  • C語(yǔ)言實(shí)現(xiàn)一個(gè)通訊錄

    C語(yǔ)言實(shí)現(xiàn)一個(gè)通訊錄

    這篇文章主要為大家詳細(xì)介紹了用C語(yǔ)言實(shí)現(xiàn)一個(gè)通訊錄,具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下
    2018-02-02
  • C++非繼承時(shí)函數(shù)成員訪問(wèn)屬性和類繼承過(guò)程中的訪問(wèn)控制

    C++非繼承時(shí)函數(shù)成員訪問(wèn)屬性和類繼承過(guò)程中的訪問(wèn)控制

    這篇文章主要介紹了C++非繼承時(shí)函數(shù)成員訪問(wèn)屬性和類繼承過(guò)程中的訪問(wèn)控制,非繼承時(shí),protected成員和private成員沒(méi)有任何區(qū)別,都是類內(nèi)部可以直接訪問(wèn)它們、類外部的類對(duì)象不可訪問(wèn)它們、類內(nèi)部的類對(duì)象可以訪問(wèn)它們,更多詳細(xì)內(nèi)容請(qǐng)參考下面相關(guān)資料
    2022-03-03
  • C語(yǔ)言return, exit, abort的區(qū)別

    C語(yǔ)言return, exit, abort的區(qū)別

    這篇文章主要介紹了C語(yǔ)言return, exit, abort的區(qū)別,一般情況下,在C語(yǔ)言中退出一個(gè)程序用return,如果在main函數(shù)中,return在清理局部對(duì)象之后,會(huì)調(diào)用exit函數(shù),和return相比,exit并不會(huì)銷毀局部對(duì)象,下面一起進(jìn)入文章了解更詳細(xì)內(nèi)容吧,需要的朋友也可以參考一下
    2022-01-01
  • C語(yǔ)言中%c與%s的區(qū)別與劃分詳解

    C語(yǔ)言中%c與%s的區(qū)別與劃分詳解

    這篇文章主要介紹了C語(yǔ)言中%c與%s的區(qū)別與劃分詳解,具有很好的參考價(jià)值,希望對(duì)大家有所幫助。一起跟隨小編過(guò)來(lái)看看吧
    2020-12-12
  • 詳解C++構(gòu)造函數(shù)

    詳解C++構(gòu)造函數(shù)

    這篇文章主要為大家介紹了C++構(gòu)造函數(shù),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下,希望能夠給你帶來(lái)幫助
    2021-11-11
  • C++實(shí)現(xiàn)推箱子小游戲源碼

    C++實(shí)現(xiàn)推箱子小游戲源碼

    這篇文章主要為大家詳細(xì)介紹了C++實(shí)現(xiàn)推箱子小游戲源碼,文中示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下
    2019-07-07
  • Qt實(shí)現(xiàn)指針式時(shí)鐘 Qt實(shí)現(xiàn)動(dòng)態(tài)時(shí)鐘

    Qt實(shí)現(xiàn)指針式時(shí)鐘 Qt實(shí)現(xiàn)動(dòng)態(tài)時(shí)鐘

    這篇文章主要為大家詳細(xì)介紹了Qt實(shí)現(xiàn)指針式時(shí)鐘,Qt實(shí)現(xiàn)動(dòng)態(tài)時(shí)鐘,兩者相互切換,文中示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下
    2020-07-07
  • C++實(shí)現(xiàn)貪吃蛇游戲

    C++實(shí)現(xiàn)貪吃蛇游戲

    這篇文章主要為大家詳細(xì)介紹了C++實(shí)現(xiàn)貪吃蛇游戲,文中示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下
    2020-12-12

最新評(píng)論