排序算法总结

冒泡排序

 1 void BubbleSort(ElementType A[], int N) {
 2     ElementType temp;
 3     for(int i=0; i<N; i++) {
 4         for(int j=0; j<N-i-1; j++) { // 关键点在与j<N-i-1,生成一个升序的有序表
 5             if(A[j] > A[j+1]) {
 6                 temp = A[j];
 7                 A[j] = A[j+1];
 8                 A[j+1] = temp;
 9             }
10         }
11     }
12 }

快速排序

 1 // 快排的关键点
 2 // 1、在右边找比基点小的元素，与基点位置互换
 3 // 2、在左边找大于或等于基点的元素，与基点位置互换
 4 // 3、当left与right指针相同时，则指针的位置即基点所在的最终位置
 5 void QuickSort(int arr[], int leftBound, int rightBound) {
 6     if (leftBound < rightBound) { 
 7         int left = leftBound, right = rightBound, prior = arr[leftBound];
 8         while (left < right) {
 9             while (left < right && arr[right] >= prior) right--;
10             if (left < right) arr[left++] = arr[right];
11             while (left < right && arr[left] < prior) left++;
12             if (left < right) arr[right--] = arr[left];
13         }
14         arr[left] = prior;
15         QuickSort(arr, leftBound, left - 1);
16         QuickSort(arr, left + 1, rightBound);
17     }
18 }

插入排序

void InsertSort(int A[], int N ){
    for (int i = 1; i < N; i++) {        // 第 1 个数肯定是有序的，从第 2 个数开始遍历，依次插入有序序列
        int temp = A[i];                // 取出第 i 个数，和前 i-1 个数比较后，插入合适位置
        int j = i - 1;                    // 因为前 i-1 个数都是从小到大的有序序列，所以只要当前比较的数 (array[j]) 比 temp 大，就把这个数后移一位
        while (j >= 0 && A[j] < temp) {    // 当 j < 0 或 array[j] < temp(array[i]) 时终止
            A[j + 1] = A[j];            // 将大于 temp(array[i]) 的数据后移
            j--;                        // 向前比较
        }                               // 结束循环
        A[j + 1] = temp;                // array[i]插入到正确的位置上
    }
}