計(jì)算機(jī)等級考試二級輔導(dǎo)c++常用排序算法

字號： 小 中 大

//選擇排序法SelectionSort(int arr[],int n)
    template
    void SelectionSort(T arr[],int n)
    {
    int smallIndex; //表中最小元素的下標(biāo)
    int pass,j //用來掃描子表的下標(biāo)
    T temp; //用來交換表元素的臨時變量
    //pass的范圍是0~n-2
    for (pass=0;pass    {
    //從下標(biāo)pass開始掃描子表
    smallIndex=pass;
    //j遍歷整個子表arr[pass+1]到arr[n-1]
    for(j=pass+1;j     //如果找到更小的元素,則將該位置賦值給smallIndex
     if(arr[j] smallIndex=j;
    //如果smallIndex和pass不在相同的位置
     //則將子表中的最小項(xiàng)與arr[pass]交換
     if(smallIndex!=pass)
     {
    temp=arr[pass];
    arr[pass]=arr[smallIndex];
     arr[smallIndex]=temp;
     }
    }
    }
    /************************************************************************
    雙端選擇排序算法:是上面選擇排序算法的變種,可以定位每個子表中最小和元素
    并把它們分別放在子表的開頭和結(jié)尾.
    ************************************************************************/
    //雙端選擇排序算法函數(shù)deSelSort()的實(shí)現(xiàn)
    template
    void deSelSort(T arr[],int n)
    {
    int smallIndex,largeIndex; //表中最小及元素的下標(biāo)
    int leftPass=0,rightPass=n-1,i,j;//用來從表左邊及右邊掃描子表的下標(biāo)
    T temp; //用于交換元素的臨時變量
    while (leftPass<=rightPass)
    {
    //從左邊及右邊開始掃描子表
    smallIndex=leftPass;
    largeIndex=rightPass;
    //j和i遍歷整個子表arr[LeftPass]~arr[rightPass]
    for (i=leftPass+1;i     //如果找到更小的元素,則將該位置賦值給smallIndex
     if (arr smallIndex=i;
     //如果smallIndex和leftPass不在相同的位置
    //則將子表中的最小項(xiàng)與arr[pass]交換
     if (smallIndex!=leftPass)
     {
    temp=arr[leftPass];
    arr[leftPass]=arr[smallIndex];
    arr[smallIndex]=temp;
    }
     for (j=rightPass-1;j>leftPass;j--)
     if(arr[j]>arr[largeIndex])
    largeIndex=j;