欧美性猛交XXXX免费看蜜桃,成人网18免费韩国,亚洲国产成人精品区综合,欧美日韩一区二区三区高清不卡,亚洲综合一区二区精品久久

  快速排序（Quicksort）是對冒泡排序的一種改進(jìn)。由C. A. R. Hoare在1962年提出。它的基本思想是：通過(guò)一趟排序將要排序的數據分割成獨立的兩部分，其中一部分的所有數據都比另外一部分的所有數據都要小，然后再按此方法對這兩部分數據分別進(jìn)行快速排序，整個(gè)排序過(guò)程可以遞歸進(jìn)行，以此達到整個(gè)數據變成有序序列。對于輸入的子數組a[l:r]，按以下3個(gè)步驟進(jìn)行排序。
    1）分解(divide):以a[l]為基準元素將a[l,r]劃分成3段a[l:i-1],a[i],a[i+1:r],使得a[l:i-1]中任何一個(gè)元素小于等于a[i]，a[i+1,r]中任何一個(gè)元素大于等于a[i]。下標i在劃分過(guò)程中確定。
    2）遞歸求解(conquer):通過(guò)遞歸調用快速排序算法，分別對a[l:i-1]和a[i+1:r]進(jìn)行排序。
    3）合并(merge)：由于對a[l:i-1]和a[i+1:r]的排序是就地進(jìn)行的，所以在a[l:i-1]和a[i+1:r]都已排好的序后不需要執行任何計算，a[l:r]就已排好序了。
C++實(shí)現代碼 qsort.cpp
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
using namespace std;

int partition(int*a,int,int);
void qsort(int*a, int,int);
void swap(int &,int &);

int main()
{   //測試代碼
    int num;
    cout << "輸入數組個(gè)數\n";
    cin >> num;
    int *a = new int [num];
    cout << "輸入數組元素\n";
    for(int i = 0;i <num;i++)
    {
        cin >> a[i];
    }
      qsort(a,0,num);
      for(int i = 0;i<num ;i++)
      {
              cout << "a[" << i << "] = " << a[i] << endl;
      }
      system("pause");
      return 0;
}
void qsort(int* a,int l,int r)
{
    if(l<r){
            int i = partition(a,l,r);
            qsort(a,l,i-1); //對左半段排序
            qsort(a,i+1,r); //對右半段排序
    }
}
int partition(int *a,int l,int r)
{
    int i,j,temp;

    i=l;j=r;
    temp=a[i];
    do{
       while((a[j]>temp) && (i<j))
           j--;
       if(i<j)
           swap(a[i++],a[j]);
       while((a[i]<=temp) && (i<j))
           i++;
       if(i<j)
           swap(a[j--],a[i]);
    }while(i!=j);
    a[i]=temp;
 return i;
}
void swap(int &a,int &b)
{
    int temp = a;
    a = b;
    b = temp;  
}

歸并排序(merge sort):對一個(gè)數組進(jìn)行排序，可以將之分解為n個(gè)已經(jīng)排序的子問(wèn)題，然后進(jìn)行合并就可以得到了原問(wèn)題的解。分治法的基本思想是將一個(gè)規模為n的問(wèn)題分解為k個(gè)規模較小的子問(wèn)題，這些子問(wèn)題相互獨立且與原問(wèn)題相同。遞歸的解這些子問(wèn)題，然后將個(gè)子問(wèn)題的解合并得到原問(wèn)題的解。分為三步：
    1）把大的問(wèn)題分解成小的問(wèn)題：MergeSort;
    2）把兩個(gè)較小的子問(wèn)題合并成一個(gè)較大的問(wèn)題：Merge；
    3）對已排序數組進(jìn)行拷貝：Copy;
C++實(shí)現代碼 msort.cpp
#include <iomanip.h>
#include <iostream.h>
//這個(gè)函數將b[0]至b[right-left+1]拷貝到a[left]至a[right]

void Copy(int a[],int b[],int left,int right)
{
    int size=right-left+1;
    for(int i=0;i<size;i++)
    {
        a[left++]=b[i];
    }
}
//這個(gè)函數合并有序數組a[left:i],a[i+1:right]到b,得到新的有序數組b

void Merge(int a[],int b[],int left,int i,int right)
{
    int a1cout=left,//指向第一個(gè)數組開(kāi)頭
    a1end=i,//指向第一個(gè)數組結尾
    a2cout=i+1,//指向第二個(gè)數組開(kāi)頭
    a2end=right,//指向第二個(gè)數組結尾
    bcout=0;//指向b中的元素
    for(int j=0;j<right-left+1;j++)//執行right-left+1次循環(huán)
    {
        if(a1cout>a1end){b[bcout++]=a[a2cout++];continue;}//如果第一個(gè)數組結束，拷貝第二個(gè)數組的元素到b
        if(a2cout>a2end){b[bcout++]=a[a1cout++];continue;}//如果第二個(gè)數組結束，拷貝第一個(gè)數組的元素到b
        if(a[a1cout]<a[a2cout]){b[bcout++]=a[a1cout++];continue;}//如果兩個(gè)數組都沒(méi)結束，比較元素大小，把較小的放入b
        else
        {b[bcout++]=a[a2cout++];continue;}
    }
}
//對數組a[left:right]進(jìn)行合并排序

void MergeSort(int a[],int left,int right)
{
    int *b=new int[right-left+1];
    if(left<right){
        int i=(left+right)/2;//取中點(diǎn)
        MergeSort(a,left,i);//左半邊進(jìn)行合并排序
        MergeSort(a,i+1,right);//右半邊進(jìn)行合并排序
        Merge(a,b,left,i,right);//左右合并到b中
        Copy(a,b,left,right);//從b拷貝回來(lái)
    }
}

int main()
{   //測試代碼
    int num;
    cout << "輸入數組個(gè)數\n";
    cin >> num;
    int *a = new int [num];
    cout << "輸入數組元素\n";
    for(int i = 0;i <num;i++)
    {
        cin >> a[i];
    }
    MergeSort(a,0,num);
    for(int i = 0;i<num ;i++)
    {
        cout << "a[" << i << "] = " << a[i] << endl;
    }
    system("pause");
    return 0;
}