//sort.c
void SelectionSort(double *p, int n);
int main(){
    double test[5] = {3,2,5,7,9};
    SelectionSort(test,5);
    for (int i = 0; i < 5; i++)
        printf("%f\n", test[i]);
    return 0;
}

//交換數(shù)組中i,j處的值
void mySwap(double *arr, int i, int j){
    double temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

//選擇排序
void SelectionSort(double *arr, int n){
    int pMax;
    double temp;
    for (int i = 0; i < n-1; i++){
        pMax = i;
        for (int j = i+1; j < n; j++)
            if (arr[j]>arr[pMax])
                pMax = j;
        mySwap(arr,pMax,i);
    }
}

//冒泡排序
void BubbleSort(double *arr, int n)
{
    n = n-1;
    double temp;
    for (int i = 0; i < n; i++)
    for (int j = 0; j < n-i; j++)
        if (arr[j]>arr[j+1])
            mySwap(arr,i,j);        /*前文定義的函數(shù)*/
}

//插入排序
void InsertionSort(double *arr, int n){
    double temp;
    int j;
    for (int i = 1; i < n; i++){
        j = i-1;
        temp  = arr[i];
        while (temp<arr[j] && j>=0){
            arr[j+1] = arr[j];      //第j個元素后移
            j--;
        }
        arr[j+1] = temp;
    }
}

//sort.c

void myMerge(double *arr, int nL, int nR);
int main(){
    int n = 6;
    double arr[6] = {2,4,5,1,3,7};
    Merge(arr,3,3);

    for (int i = 0; i < n; i++)
        printf("%f\n", arr[i]);
    return 0;
}

//兩個有序數(shù)組的混合,arr為輸入數(shù)組
//nL、nR分別為左數(shù)組和右數(shù)組的長度
void Merge(double *arr, int nL, int nR){
    nL = nL-1;                    //左側最后一個元素的索引
    int sInsert = 0;               //左側待插入起始值
    double temp;
    for (int i = 1; i <= nR; i++)
    {
        while (arr[nL+i]>arr[sInsert])
            sInsert++;
        if (sInsert<nL+i){
            temp = arr[nL+i];
            for (int j = nL+i; j > sInsert; j--)
                arr[j]=arr[j-1];
            arr[sInsert] = temp; 
        }
        else
            break;    //如果sInsert==nL+i，說明右側序列無需插入
    }
}

void MergeSort(double *arr, int n);
void myMerge(double *arr, int nL, int nR);

int main(){
    int n = 6;
    double arr[6] = {5,2,4,7,1,3};
    MergeSort(arr,n);

    for (int i = 0; i < n; i++)
        printf("%f\n", arr[i]);
    return 0;
}

void MergeSort(double *arr, int n){
    if (n>2)
    {
        int nL = n/2;
        int nR = n-nL;
        MergeSort(arr,nL);
        MergeSort(arr+nL,nR);
        Merge(arr,nL,nR);
    }
    else if(n==2)
        Merge(arr,1,1);
    //當n==1時說明數(shù)組中只剩下一個元素，所以什么也不用做
}

//希爾排序
void ShellSort(double *arr, int n){
    double temp;
    int j;
    for (int nSub = n/2; nSub >0; nSub/=2)      //nSub為子數(shù)組長度
        for (int i = nSub; i < n; i++)
        {
            temp = arr[i];
            for (j = i-nSub; j >= 0&& temp<arr[j]; j -= nSub)
                arr[j+nSub] = arr[j];
            arr[j+nSub] = temp;
        }
}

//快速排序
void QuickSort(double *arr, int n){
    double pivot = arr[0];      //選取第0個點為基準
    int i = 1;
    int j = n-1;
    while (i<j){
        if (arr[i]<pivot)
            i++;
        else{
            mySwap(arr,i,j);
            j--;
        }
    }
    if (arr[i]>pivot)
        i--;
    mySwap(arr,i,0);
    if (i>1)
        QuickSort(arr,i);    //對i前的數(shù)組進行快排
    
    i++;
    if (i<n-1)
        QuickSort(arr+i,n-i);//對i+1后的數(shù)組進行快排
}

//如果堆中節(jié)點號為m的點不滿足要求，則調整這個點
//此為最大堆
void adjustHeap(double *arr, int m, int n){
    int left = m*2+1;       //左節(jié)點

    while (left<n)
    {
        if (left+1<n)       //判斷右節(jié)點
            if (arr[left]<arr[left+1])
                left++;     //當右節(jié)點大于左節(jié)點時，left表示右節(jié)點
        
        if (arr[m]>arr[left])
            break;          //如果父節(jié)點大于子節(jié)點，則說明復合最大堆
        else{
            mySwap(arr,m,left);
            m = left;
            left = m*2+1;
        }
    }
}

//堆排序
void HeapSort(double *arr, int n){
    for (int i = n/2; i >= 0; i--)
        adjustHeap(arr,i,n);        //初始化堆
    for (int i = n-1; i > 0 ; i--){
        mySwap(arr,0,i);            //將待排序元素放到最頂端
        adjustHeap(arr,0,i);        //調整最頂端的值 
    }   
}

/計數(shù)排序,輸入數(shù)組為整數(shù)
void CountingSort(int *arr,int n){
    int aMax = arr[0];
    int aMin = arr[0];
    for (int i = 0; i < n; i++) //查找最大值和最小值
        if (arr[i]>aMax)
            aMax = arr[i];
        else if (arr[i]<aMin)
            aMin = arr[i];
    
    int m = aMax-aMin+1;         //索引長度
    int *arrSort = (int*)malloc(sizeof(int)*m);
    for (int i = 0; i < m; i++)
        arrSort[i]=0;           //初始化索引
    
    for (int i = 0; i < n; i++) //排序
        arrSort[arr[i]-aMin] += 1;
    
    n = 0;
    for (int i = 0; i < m; i++)
    {
        aMax = i+aMin;          //此值為真實數(shù)據(jù)
        for (int j = n; j < n+arrSort[i]; j++)
            arrSort[j] = i+aMin;
        n += arrSort[i];
    }
}