#include <stdio.h>
#include <stdlib.h>
typedef enum{RED,WHITE,BLUE} color;
//交换函数
void Swap(color &a,color &b){
    color temp;
    temp=a;
    a=b;
    b=temp;
}
//ShellSort(基本思想:将数组用不同的步长划分为不同的子表，对子表内部进行相关的排序，使得子表间有序，最后设置步长为1，进行一次直接插入排序)
void ShellSort(int A[],int n){
    int i,j,dk;
    //步长变化
    for(dk=n/2;dk>=1;dk=dk/2){
        //开始遍历子表中的元素
        for(i=dk+1;i<=n;i++){
            if(A[i]<A[i-dk]){
                //暂存元素
                A[0]=A[i];
                //后移元素
                for(j=i-dk;j>0 && A[j]>A[0];j-=dk)
                    A[j+dk]=A[j];
                A[j+dk]=A[0];
            }
        }
    }
}
//ShellSort
void ShellSort1(int A[],int n){
    int i,j,dk;
    //步长变化
    for(dk=n/2;dk>=1;dk=dk/2){
        //遍历子表
        for(i=dk+1;i<=n;i+=dk){
            if(A[i]>A[i-dk]){
                A[0]=A[i];
                //后移元素
                for(j=i-dk;j>0 && A[j]>A[0];j-=dk){
                    A[j+dk]=A[j];
                }
                A[j+dk]=A[0];
            }
            i++;
        }
    }
}
//BubbleSort(基本思路:将每个元素相邻位置比较，小的元素上升)
void BubbleSort(int A[],int n){
    int i,j,temp;
    //从第一个变量开始遍历
    for(i=0;i<n-1;i++){
        //设置变量
        bool flag=false;
        //必交趟数
        for(j=n-1;j>i;j--){
            //比较大小
            if(A[j-1]>A[j]){
                temp=A[j];
                A[j]=A[j-1];
                A[j-1]=temp;
                flag=true;
            }
        }
        //这趟没有比较直接，说明有序，直接return
        if(flag==false)
            return;
    }
}
void Print(int A[],int n){
    for(int i=0;i<n;i++){
        printf("%d\t",A[i]);
    }
    printf("\n");
}
//QuickSort(基本思想:找到一个中枢元素作为分界点，将小于中枢元素的数值放在左边，大于中枢元素的数值放在右边)
int Partition(int A[],int low,int high){
    //设置中枢元素
    int pivots=A[low];
    //小于中枢元素的元素放在A[low]位置
    while(low<high){
        while(low<high && A[high]>=pivots) high--;
        A[low]=A[high];
        while(low<high && A[low]<=pivots) low++;
        A[high]=A[low];
    }
    A[low]=pivots;
    return low;
}
void QuickSort(int A[],int low,int high){
    if(low<high){
        int pivotspaos=Partition(A,low,high);
        QuickSort(A,low,pivotspaos-1);
        QuickSort(A,pivotspaos+1,high);
    }
}
//双向起泡(基本思路:分别从头部和尾部开始遍历，尾部为最大数值，头部为最小数值)
void DoubleBubbleSort(int A[],int n){
    int i,j,temp,low=0,high=n-1;
    bool flag=true;
    while(flag && low<high){
        //设置标记
        flag=false;
        //从前往后遍历
        for(i=low;i<high;i++){
            if(A[i]>A[i+1]){
                temp=A[i];
                A[i]=A[i+1];
                A[i+1]=temp;
                flag=true;
            }
        }
        //让high--，表示有一个元素不需要比较了
        high--;
        for(j=high;j>low;j--){
            if(A[j-1]>A[j]){
                temp=A[j-1];
                A[j-1]=A[j];
                A[j]=temp;
                flag=true;
            }
        }
        //low++
        low++;
    }
}
//将数组中奇数放在偶数之前(基本思想：利用快速排序的思想，双指针遍历，从后面找奇数，从前面开始找偶数，然后分别交换)
void Move(int A[],int n){
    int i=0,j=n-1,temp;
    //当i<j
    while(i<j){
        //前面开始找偶数
        while(i<j && A[i]%2!=0) i++;
        //后面开始找奇数
        while(i<j && A[j]%2==0) j--;
        if(i<j){
            temp=A[i];
            A[i]=A[j];
            A[j]=temp;
        }
        i++;
        j--;
    }
}
//查找元素(利用快速排序和递归实现快速查找一个指定下标的元素)
int kth_elem(int A[],int low,int high,int k){
    //第一部分:快速排序
    int pivots=A[low];
    int low_temp=low,high_temp=high;
    while(low<high){
        while(low<high && A[high]>=pivots) high--;
        A[low]=A[high];
        while(low<high && A[low]<=pivots) low++;
        A[high]=A[low];
    }
    A[low]=pivots;
    //第二部分:递归快排，找到对应的元素
    if(k==low)
        return A[low];
    else if(k<low)
        return kth_elem(A,low_temp,low-1,k);
    else
        return kth_elem(A,low+1,high_temp,k);
}
//荷兰国旗问题
void Flag_Arrange(color a[],int n){
    int i=0,j=0,k=n-1;
    while(j<k){
        //判断是什么颜色
        switch (a[j]) {
            case RED:Swap(a[j],a[i]);i++;j++;break;
            case WHITE:j++;break;
            case BLUE:Swap(a[j],a[k]);k--;
        }
    }
}
int main() {
    int A[]={3,2,34,1,23,4,1};
    Print(A,7);
    //QuickSort(A,0,6);
    //BubbleSort(A,7);
    //DoubleBubbleSort(A,7);
    //Move(A,7);
    printf("%d\n",kth_elem(A,0,6,34));
    Print(A,7);
    return 0;
}