排序算法学习笔记

1. 插入排序

• 算法稳定、时间复杂度为n^2

    void insertSort (DataType D[], int length) {
        DataType key;
        for(int j=2; j<length; j++) {
            key = D[j];
            int i = j - 1;
            while(i>0 && key < D[i]) {
                D[i+1] = D[i];
                i = i-1;
            }
           D[i+1] = key;
       }
    }

2. 冒泡排序

• 算法稳定，时间复杂度为n^2

void bubbleSort(int[] arr){  
        int temp = 0;  
        for(int i=0;i<arr.length-1;i++){  
            for(int j=arr.length-1;j>i;j--){  
                if(arr[j]<arr[j-1]){  
                    temp = arr[j-1];  
                    arr[j-1] = arr[j];  
                    arr[j] = temp;  
                }  
            }  
        }  
    }  

3. 选择排序

• 算法不稳定，时间复杂度为n^2

void selectSort (T data, int n) {
    int i = 1, j;
    int max;
    while (i < n-1) {
        max = n-i;
        for (j=0; j<n-i+1;j++) {
            if (data[j] > data[max]) {
                max = j;
            }
        }
        if (max!=n-i) {
            swap(data[max], data[n-i]);   
        }
        i++;
    }
}

4. 快速排序

• 算法不稳定，通常情况时间复杂度为nlogn

5. 归并排序

6. 希尔排序

• 算法不稳定，一般认为时间复杂度在nlogn与n^2之间，不适用于链表结构

7. 堆排序

• 算法不稳定，最坏时间复杂度为nlogn