天天看點
傳回

面試常考的排序算法

數值算法: 解方程、微積分、有限元分析、信号處理,等等
非數值算法: 排序、查找

一、冒泡排序:

1、算法:

9,7,5,3,1

掃描1:   7,5,3,1,9

掃描2:   5,3,1,7,9

…

掃描N-1:  1,3,5,7,9

  • (1) 比較相鄰的元素, 如果第一個比第二個大, 就交換它們兩個
  • (2) 對每一對相鄰元素做同樣的工作, 從開始的第一對到結尾的最後一對. 經過這一步, 最後的元素将是最大值
  • (3) 針對所有的元素重複以上步驟, 除了最後一個
  • (4) 持續每次對越來越少的元素重複以上步驟, 直至沒有元素需要交換
範例: 
#include <stdio.h>

void bubble_sort(int data[], size_t size)
{
    size_t i;  // 第幾趟
    for (i = 0; i < size - 1; ++i) {
        int ordered = 1;
        size_t j;  // 第幾次
        for (j = 0; j < size - 1 - i; ++j) {
            if (data[j+1] < data[j]) {
                data[j] = data[j] ^ data[j+1];
                data[j+1] = data[j] ^ data[j+1];
                data[j] = data[j] ^ data[j+1];
                ordered = 0;
            }
        }

        if (ordered) {
            break;
        }
    }
}

int main(void)
{
    int data[] = {9,0,7,2,5,4,3,6,1,8};
    size_t size = sizeof(data) / sizeof(data[0]);

    bubble_sort(data, size);

    size_t i;
    for (i = 0; i < size; ++i) {
            printf("%d ", data[i]);
    }
    printf("\n");
    return 0;
}

/*
Output:

0 1 2 3 4 5 6 7 8 9 

*/

2、評價:

平均時間複雜度,O(N^2)，穩定，對資料有序性非常敏感。

穩定是指 資料相同的元素,順序不變

對資料敏感是指 資料越接近有序,消耗時間越短, 越接近逆序,消耗時間越長

二、插入排序

1、算法

  • (1) 從第一個元素開始, 該元素可以認為已經被排序
  • (2) 取出下一個元素, 在已經排序的元素序列中從後向前掃描
  • (3) 若該元素大于新元素, 則将該元素移到下一位置
  • (4) 若該元素小于或等于新元素, 則将新元素插入到該元素後
  • (5) 重複步驟2, 直至處理完所有元素
範例: 
void insert_sort(int data[], size_t size)
{
    size_t i;
    for (i = 1; i < size; ++i) {
        int temp = data[i];
        size_t j;
        for (j = i; j - 1 >= 0; --j) {
            if (data[j-1] > temp) {
                data[j] = data[j-1];
            }
            else {
                data[j] = temp;
                break;
            }
        }
    }
}

2、評價:

平均時間複雜度, O(N^2)，穩定，對資料有序性非常敏感。

冒泡排序是值交換, 而插入排序是值移動, 是以插入排序要優于冒泡排序。

三、選擇排序

1、算法:

首先在未排序序列中找到最小元素, 存放到排序序列的起始位置, 然後, 再從剩餘未排序元素中繼續尋找最小元素, 然後放到排序序列末尾. 以此類推, 直到所有元素均排序完畢.

範例: 
void select_sort(int data[], size_t size)
{
    size_t i;
    for (i = 0; i < size - 1; ++i) {
    	int k = i;
            for (int j = i + 1; j < size; ++j) {
                if (data[j] < data[k]) {
                    k = j;
                }
            }

            if (k != i) {
                data[i] = data[i] ^ data [k];
                data[k] = data[i] ^ data [k];
                data[i] = data[i] ^ data [k];
            }
    }
}

2、評價:

平均時間複雜度, O(N^2)，不穩定。

對資料有序性不敏感。雖然比較次數多, 但資料交換少, 是以一般情況下快于冒泡排序。

四、快速排序

1、算法:

  • (1) 從數列中挑出一個元素, 成為基準;
  • (2) 重新排序數列, 所有比基準小的元素擺放在基準前面, 所有比基準大的元素擺在基準的後面(相同的元素可以放在任一邊), 這個過程稱為分區
  • (3) 以遞歸方式對小于基準的元素分區和大于基準的元素分區分别進行排序
範例: 
void quick_sort(int data[], size_t left, size_t right)
{
    size_t p = (left + right) / 2;
    int pivot = data[p];
    size_t i = left, j = right;
    // i 向右走, j 向左走 當兩者重合終止
    while (i < j) {
        for (; !(i >= p || pivot < data[i]); ++i) {}  // 小括号裡是離開for循環的條件
        if (i < p) {
            data[p] = data[i];
            p = i;
        }

        for (; !(j <= p || data[j] < pivot); --j) {}
        if (j > p) {
            data[p] = data[j];
            p = j;
        }
    }
    data[p] = pivot;

    if (p - left > 1) {
        quick_sort(data, left, p-1);
    }

    if (right - p > 1) {
        quick_sort(data, p + 1, right);
    }
}

2、評價:

平均時間複雜度, O(NlogN)，N*log2底N的對數。不穩定, 如果每次能均分劃分序列, 它是最快的排序算法。

每次大于基準值的個數和小于基準值的個數相差很小, 消耗時間越少。

範例2:   實作C标準庫中的快速排序方法 
void quick_sort2(void* base, size_t left, size_t right, size_t size, 
	int(*compar)(const void*, const void*))
{
    // 把pb指向的size個位元組,copy到pa
    // memcpy(pa, pb, size);
    // compar函數指針, -1代表參數1小于參數2, 0代表相等, 1代表參數1大于參數2

    size_t p = (left + right) / 2;
    void* pivot = malloc(size);
    memcpy(pivot, base + p * size, size);
    size_t i = left, j = right;
    while (i < j) {
        for (; !(i >= p || compar(base+i*size, pivot) > 0); ++i) {}
        if (i < p) {
            memcpy(base+p*size, base+i*size, size);
            p = i;
        }

        for (; !(j <= p || compar(base+j*size, pivot) < 0); --j) {}
        if (j > p) {
            memcpy(base+p*size, base+j*size, size);
            p = j;
        }
    }
    
    memcpy(base + p * size, pivot, size);
    free(pivot);
    if (p - left > 1) {
    	quick_sort2(base, left, p - 1, size, compar);
    }

    if (right - p > 1) {
    	quick_sort2(base, p + 1, right, size, compar);
    }
}

void myqsort(void* base, size_t nmemb, size_t size, 
	int(*compar)(const void*, const void*))
{
    quick_sort2(base, 0, nmemb - 1, size, compar);
}

int main(void)
{
    int na[] = {55,23,65,2,4,75};
    size_t size = sizeof(na[0]);
    size_t numb = sizeof(na) / size;
    // c标準庫的函數qsort
    //qsort(na, numb, size, cmpint);
    myqsort(na, numb, size, cmpint);

    size_t i;
    for (i = 0; i < numb; ++i) {
        printf("%d ", na[i]);
    }
    printf("\n");

    const char* sa[] = {"daf", "ddeee", "rre", "awq", "bbfu"};
    size = sizeof(sa[0]);
    numb = sizeof(sa) / size;
    //qsort(sa, numb, size, cmpstr);
    myqsort(sa, numb, size, cmpstr);

    for (i = 0; i < numb; ++i) {
        printf("%s ", sa[i]);
    }
    printf("\n");

    return 0;
}

/*
Output:

2 4 23 55 65 75 
awq bbfu daf ddeee rre 

*/

五、歸并排序

1、算法:

  • (1) 申請空間, 使其大小為兩個已經排序序列之和, 該空間用來存放合并後的序列
  • (2) 設定兩個指針, 最初位置分别為兩個已經排序序列的起始位置
  • (3) 比較兩個指針所指向的元素,選擇相對小的元素放入到合并空間, 并移動指針到下一個位置
  • (4) 重複步驟3直到某一指針達到序列尾
  • (5) 将另一序列剩下的所有元素直接複制到合并序列尾

2、評價:

平均時間複雜度, O(2NlogN)。穩定, 對資料有序性不敏感. 非就地排序, 需要與待排序序列一樣多的輔助空間,

不适用于大資料量的排序。

範例： 
// 實作一個外部合并功能的函數, data1和data2都是有序的
void outer_merge(int data1[], size_t size1, int data2[], size_t size2, int data3[]) {
    size_t i = 0, j = 0, k = 0;
    for (;;) {
        if (i < size1 && j < size2) {
            if (data1[i] < data2[j]) {
                data3[k++] = data1[i++];
            }
            else {
                data3[k++] = data2[j++];
            }
        }
        else if (i < size1) {
            data3[k++] = data1[i++];
        }
        else if (j < size2) {
            data3[k++] = data2[j++];
        }
        else {
            break;
        }
    }
}

// 實作一個内部合并功能的函數, left到mid有序, mid+1到right有序, 實作left到right有序
void inner_merge(int data[], size_t left, size_t mid, size_t right) {
    size_t size = (right - left + 1) * sizeof(int);
    int* merge = malloc(size);

    outer_merge(data + left, 
        mid - left + 1,
        data + mid + 1,
        right - mid,
        merge);
    memcpy(data + left, merge, size);
    free(merge);
}

// 歸并排序
void merge_sort(int data[], size_t left, size_t right) {
    if (left < right) {
        int mid = (left + right) / 2;
        merge_sort(data, left, mid);
        merge_sort(data, mid + 1, right);
        inner_merge(data, left, mid, right);
    }
}
面試 算法 資料結構
上一篇: 快速排序 常考排序算法
下一篇: java 【資料結構】常考的OJ 連結清單，重點！重點！！！0J面試題 連結清單

繼續閱讀