数组排序

数组排序

一、冒泡排序

将数组中的相邻两个元素进行比较，将比较大（较小）的数通过两两比较移动到数组末尾（开始），执行一遍内层循环，确定一个最大（最小）的数，外层循环从数组末尾（开始）遍历到开始（末尾）。

每一趟均将一个数值放在最终位置。并且之后，该数值不再参与排序。

void BubbleSort(int A[] , int n){
	int temp ;
    for(int i = 1 ; i < n  ; i ++ ){
        for(int j = 0 ; j < n - i ; j ++ ){
            if( A[j] > A[j+1] ){ //大的数字后移
                temp = A[j] ;
                A[j] = A[j+1] ;
                A[j+1] = temp ;
            }
        }
    }
}

时间复杂度：O(n^2)

空间复杂度：O(1)

稳定排序

二、选择排序

将要排序的数组分成两部分，一部分有序的，一部分是无序的，从无序的部分取出最值放到已经排序的最后。

void SelectSort(int A[] , int n ){
    int temp = 0 ;
    for(int i = 0 ; i < n - 1 ; i ++ ){
        int min = i ;
        //找出后续数组中最小的值
        for(int j = i + 1 ; j < n ; j ++ ){   
            if( A[min] > A[j])
                min = j ;
        }
        //交换位置
        if( min != i ){
            temp = A[min] ;
            A[min] = A[i] ;
            A[i] = temp ;
        }
    }
}

时间复杂度：O(n^2)

空间复杂度：O(1)

不稳定排序

三、插入排序

将要排序的数组分成两部分，每次从后面的部分取出索引最小的元素插入到前一部分的适当位置。

存在大量的移动操作。

void InsertSort(int A[] , int n ){
    int temp = 0 ;
    for(int i = 1 ; i < n ; i ++ ){
        temp = A[i] ;
        int j = i - 1 ;
        while(j >= 0 && temp < A[j]){
            A[j+1] = A[j] ;
        	j -- ;
        }
        A[j+1] = temp ;
    }
}

时间复杂度：O(n^2)

空间复杂度：O(1)

稳定排序

四、快速排序

快速排序法号称是目前最优秀的算法之一，实现思路是，将一个数组的排序问题看成是两个小数组的排序问题，而每个小的数组又可以继续看成更小的两个数组，一直递归下去，直到数组长度大小最大为2。

void QuickSort(int A[] , int left , int right ){
    if(left < right ){
        int i = left , j = right ;
        int priot = A[i] ;
        while( i < j ){
            while( A[j] > priot ){
                j -- ;
            }
            while( A[i] < priot ){
                i ++ ;
            }
            int temp = A[j] ;
            A[j] = A[i] ;
            A[i] = temp ;
        }
        A[i] = priot ;
        QuickSort(A , left , i-1 );
        QuickSort(A , i+1 , right);
    }
}

时间复杂度：O(n·logN) 最差时间复杂度：O(n^2)

空间复杂度：O(1)

不稳定排序

五、桶排序

桶中出现的数组元素都做个标记1，然后将桶数组中有1标记的元素依次打印。

void BucketSort(int A[] , int n , int max){
    int bucket[max+1] = {0} ;
    for(int i = 0 ; i < n ; i ++ ){
        bucket[ A[i] ] ++ ;
    }
    for(int j = 0 ; j < max ; j ++ ){
        while(bucket[j] > 0){
            printf("%d",j) ;
            bucket[j] -- ;
        }
    }
}

时间复杂度：O(n)

空间复杂度：O(max(element))

六、希尔排序

性能最好的排序

void ShellSort(int A[] , int n ){
    int interval = n/2 ;
    while( interval > 0 ){
        for(int i = interval ; i < n ; i ++ ){
            int temp = A[interval] ; 
            for(int j = i - interval ; j >=0 ; j -= interval ){
                if( A[j] > temp ){
                    A[j+interval] = A[j] ;
                }else{
                    break;
                }
            }
            A[j+interval] = temp ;
  	  	}
        interval /=2 ;
    }
}

时间复杂度：O(n·logn)

空间复杂度：O(1)

不稳定排序

七、归并排序

归并排序（Merge Sort）是建立在归并操作上的一种有效，稳定的排序算法，该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。

void MergeSort(int A[] , int left, int right ){
    if(left >= right )
        return;
    int mid = (left + right)/2 ;
    
    MergeSort(A,left,mid);
    MergeSort(A,mid+1,right);
    Merge(A,left,right,mid);
}
void Merge(int A[] , int left ,int right , int mid ){
    int B[right-left + 1] = {0};
    int i = left , j = mid+1 ;
    int k = 0 ;
    while( i<=mid && j<=right ){
        if(A[i] < A[j]){
            B[k++] = A[i++] ;
        }else{
            B[k++] = A[j++] ;
        }
    }
    while(i<=mid){
        B[k++] = A[i++];
    }
    while(j<=right){
        B[k++] = A[j++];
    }
}

时间复杂度：O(n·logn)

空间复杂度：O(n)

稳定排序

结语

以上总结可能存在错误，望指正。