第十一章排序

内排序，外排序，就地排序

插入排序：包括直接插入排序和希尔排序，插入排序都涉及到移动元素的操作。

直接插入排序，r[0-(i-1)]是已经排序的元素，r[i-(n-1)]是没有排序的元素，将r[i]插入到已经排好序的部分，涉及移动元素的操作。

void insertsort(int data[],int number){

    int temp;

    for(int i=1;i

        temp=data[i];

        int j=i-1;

        while((temp<=data[j])&&(j>=0)){

            data[j+1]=data[j];

            j--;

        }

        data[j+1]=temp;

    }

}

 

希尔排序又称缩小增量排序，实际上还是一种插入排序，是不稳定的排序，时间复杂度是o(nlogn);

void shellsort(int *array,int n){

    int gap = n/2;

    while(gap>0){

       for(int i = 0 ; i < n ; ++i){

           for(int j = i ; j < n ; j+=gap){

              if(array[j]<array[j+1]){

                  int temp = array[j];

                  array[j] = array[j+1];

                  array[j+1] = temp;

              }

           }

       }

       gap/=2;

    }

}

交换排序：冒泡排序，快速排序，涉及到交换元素

冒泡排序

void bubblesort(int *array,int n){

    for(int i = 1;i

       for(int j = n-1;j>=i;--j){

           if(array[j]>array[j-1]){

              int temp = array[j];

              array[j] = array[j-1];

              array[j-1] = temp;

           }

       }

    }

}

快速排序：

void quicksort(int *data,int start,int end){

    int i=start;

    int j=end;

    int temp;

    int middle=data[(start+end)/2];

    do{

        while(data[i]

            i++;

        while(data[j]>middle&&j>start)

            j--;

        if(i<=j){

            temp=data[i];

            data[i]=data[j];

            data[j]=temp;

            i++;

            j--;

        }

    }while(i<=j);

    if(j>start)//当左边还有值的时候，循环左边

        quicksort(data,start,j);

    if(i当右边还有值的时候，循环右边

        quicksort(data,i,end);

}

选择排序：直接选择排序，堆排序

直接选择排序

void selectsort(int *data,int number){//选择排序

    for(int i=0;i

        int flag=data[i];

        int num=i;

        for(int j=i+1;j

            if(data[j]

                flag=data[j];

                num=j;   

            }

        }

        data[num]=data[i];

        data[i]=flag;

    }

}

堆排序

void sift(int *array,int s,int n){

    int i = s;

    int j = 2*i;

    int temp = array[i];

    while(j

       if(array[j]<array[j+1])

           j+=1;

       if(temp<array[j]){

           array[i] = array[j];

           array[j] = temp;

           i = j;

           j = 2*i;

       }

       else

           j = n+1;

    }

}

void heapsort(int *array,int n){

    int i;

    for(i = n/2;i>=0;--i){

       sift(array,i,n);

    }

    for(i = n-1 ; i>=0;--i){

       int temp = array[i];

       array[i] = array[0];

       array[0] = temp;

       sift(array,0,i-1);

    }

}

双向冒泡排序算法，需要用一个标志来标志有没有需要交换的元素

void dbubble(int *array,int n){

    int i = 0;

    int j;

    int b = 1;

    while(b){

       b = 0;

       for(j = n-i-1;j>=i;j--){

           if(array[j]<array[j-1]){

              b = 1;

              int temp = array[j];

              array[j] = array[j-1];

              array[j-1] = temp;

           }

       }

       for(j = i;j

           if(array[j]>array[j+1]){

              b = 1;

              int temp = array[j];

              array[j] = array[j+1];

              array[j+1] = temp;

           }

       }

       i++;

    }

}

奇偶交换排序

void oesort(int *array,int n){

    int i = 0;

    int j;

    int b = 1;

    while(b){

       b = 0;

       for(j = 0;j

           if(array[j]>array[j+1]){

              b = 1;

              int temp = array[j];

              array[j] = array[j+1];

              array[j+1] = temp;

           }

           j++;

       }

       for(j = 1;j

           if(array[j]>array[j+1]){

              b = 1;

              int temp = array[j];

              array[j] = array[j+1];

              array[j+1] = temp;

           }

           j++;

       }

    }

}