數據結構之常見的排序算法c語言實現

    常見的簡單排序算法有冒泡排序、選擇排序、插入排序、快排、堆排序、歸并排序、希爾排序等，這些排序的理論在網上有很多，這就只給出常見的排序算法源碼，上學時候寫的，不足之處歡迎大家指正。

    下面幾種排序的主函數入口為：

    int main(int argc, char* argv[])    
    {
    	int i, len;
    	int a[] = {8,5,6,4,9,10,3,15,2,17};
    
    	len = (sizeof(a) / sizeof(a[0]));
    
    	printf("before sort \n");
    	for (i = 0 ; i < len; i++) {
    	    printf("%d,", a[i]);
    	}
    	printf("\n");
    
    	bubb_sort(a, len);
    	select_sort(a, len);
    	inert_sort(a, len);
    
    	printf("after sort \n");
    	for (i = 0 ; i < len; i++) {
    	    printf("%d,", a[i]);
    	}
    	printf("\n");
    
    	return 0;
    }

    1、冒泡排序

    static void swap(int *x, int *y)    
    {
    	int tmp;
    
    	tmp = *x;
    	*x = *y;
    	*y = tmp;
    } 

    void bubb_sort(int array[], int arr_len)
    {
    	int i, j;
    	int flag; 	
    
    	for (i = 0; i < arr_len; i++) {
    	    flag = 0; /* identify the existing array is sorted or not */	
    	    for (j = 0 ; j < arr_len - i - 1; j++) {
    	        if (array[j] > array[j + 1]) {
    	            swap(&array[j], &array[j + 1]);
    		    flag = 1;
    		}
    	    }
    	    if (flag == 0) {
    	        break;
    	    } 
    	}
    }

    上面的代碼為了加快比較速度，引入了變量flag，當無數據交換發生時，表示數據已經是有序的了，則可以直接結束排序。    

    2、選擇排序

    void select_sort(int array[], int arr_len)
    {
        int tmp;
        int i, j;
    
        for (i = 0; i < arr_len; i++) {
            tmp = i;
            for (j = i + 1; j < arr_len; j++) {
                if (array[j] < array[tmp]) {
                    tmp = j;
                }
            }
            if (tmp != i) {
                swap(&array[tmp], &array[i]);   
            } 
        }
    }

    3、插入排序

    void inert_sort(int array[], int arr_len)    
    {
        int i, j;
        int tmp;
    
        for (i = 1; i < arr_len; i++) {
            tmp = array[i];
            j = i - 1;
    
            while ((j >= 0) && (array[j] > tmp)) {
                array[j + 1] = array[j];
                --j;
            }
            array[j + 1] = tmp;
        }
    }
    以上三種排序算法，時間復雜度都為O(n2).

    4、堆排序

    #define LEFT_CHILD(i) (2*(i) + 1)    
    
    void percdown(int a[],int i,int n)
    {
        int temp,child;
    
        for (temp = a[i]; LEFT_CHILD(i) < n ; i = child) {
            child = LEFT_CHILD(i);
            if (child != n-1 && a[child] < a[child + 1]) {
                child ++;	
            }
            
            if (temp < a[child]) {
                a[i] = a[child];
            } else {
                break;
            }
        }
        a[i] = temp;
    }
    
    void heap_sort(int a[], int n)
    {
        int i;
        /* 建立堆 */
        for (i = n/2; i >= 0; i--) {
            percdown(a,i,n);
        }
        /* 刪除最大值到堆的最后單元 */
        for (i = n-1; i>0; i--) {
            swap(&a[i],&a[0]);
            percdown(a,0,i);
        }
    }

    5、希爾排序

    void shell_queue(int array[], int arr_len)    
    {
        int gap, m, n, k;
    
        gap = (arr_len / 2);
    
        while (gap > 0) {
            for (k = 0; k < gap; k++) {
                for (n = k + gap; n < arr_len; n += gap) {
                    for (m = n - gap; m >= k; m -= gap) {
                        if (array[m] > array[m+gap]) {
                        	swap(&array[m], &array[m+gap]);	
                        } else {
                            break;
                        }
                    }
                }
            }
            gap /= 2;
        }
    }
    希爾排序和插入排序有點類似，上面的代碼嵌套層數有點多，不太容易弄明白，帶入幾個數值試試就好了。

    6、快速排序    

    int mid_data(int array_a[], int left, int right)    
    {
        int mid;
    
        mid = (left + right) / 2;
    
        if (array_a[left] > array_a[right]) {
            swap(&array_a[left], &array_a[right]);
        }
        
        if (array_a[left] > array_a[mid]) {
            swap(&array_a[left], &array_a[mid]);
        }
        
        if (array_a[mid] > array_a[right]) {
            swap(&array_a[mid], &array_a[right]);
        }
    
        swap(&array_a[mid], &array_a[right-1]);
    
        return array_a[right-1];
    }
    
    
    void insertion_sort(int array[], int len)  
    {  
        int tmp, i, j;
    
        for (i = 1; i < len; i++) {
            tmp = array[i];  
            for (j = i; (j  > 0) && (tmp < array[j-1]); j--) {
            	array[j] = array[j-1];
            }
            array[j] = tmp;  
        }  
    }  
    
    void q_sort(int array_a[],int left,int right)
    {
        int i,j;
        int mid;
    
        if ((left + 3) <= right) {
            mid = mid_data(array_a, left, right);
            i = left; 
            j = right-1;
    
            while (1) {
                while(array_a[++i] < mid);
                while(array_a[--j] > mid);
                
                if (i <= j) {
                    swap(&array_a[i], &array_a[j]);
                }
                else {
                    break;
                }
            }
            swap(&array_a[i], &array_a[right-1]);
            
            q_sort(array_a, left, i - 1);
            q_sort(array_a, i + 1, right);
        } else {
            insertion_sort(array_a + left, right - left + 1);
        }
    }
    
    void quick_sort(int array[],int arr_len)
    {
        q_sort(array, 0, arr_len - 1);
    }
    快速排序是比較常用比較算法，先選取中值得時候很重要，本段代碼采用中間和首位的數值去中間的值。