天天看點
傳回

資料結構 排序算法 筆記

/*
折半插入排序是對插入排序的一種改進，主要思想是在查找插入位置的過程中
引入折半查找算法思想，利用折半查找在有序集中确定待排序元素的插入位置
與直接插入排序的差別：
    直接插入排序是從右到左按順序查找插入位置。
    折半插入排序是在有序集中查找插入位置。
*/

# include <stdio.h>
# define LEN 6

void Half_Insert_Sort(int arr[], int n);

int main(void)
{
    int arry[LEN] = {6, 2, 4, 1, 5, 9};
    int i;
    for (i = 0; i < LEN; ++i)
        printf("%-5d", arry[i]);
    printf("\n");
    Half_Insert_Sort(arry, LEN);
    for (i = 0; i < LEN; ++i)
        printf("%-5d", arry[i]);
    printf("\n");
    
    return 0;
}

void Half_Insert_Sort(int * arr, int n)
{
    int i, j, temp;
    int low, mid, high;
    for (i = 1; i < n; ++i)
    {
        temp = arr[i];
        for (low = 0, high = i - 1; high >= low; )
        {
            mid = (low + high) / 2;
            if (temp < arr[mid])
                high = mid - 1;
            else
                low = mid + 1;
        }
        for (j = i-1; j >= low; --j)
            arr[j + 1] = arr[j];
        arr[low] = temp;
    }

    return;
}/*
折半插入排序是對插入排序的一種改進，主要思想是在查找插入位置的過程中
引入折半查找算法思想，利用折半查找在有序集中确定待排序元素的插入位置
與直接插入排序的差別：
    直接插入排序是從右到左按順序查找插入位置。
    折半插入排序是在有序集中查找插入位置。
*/

# include <stdio.h>
# define LEN 6

void Half_Insert_Sort(int arr[], int n);

int main(void)
{
    int arry[LEN] = {6, 2, 4, 1, 5, 9};
    int i;
    for (i = 0; i < LEN; ++i)
        printf("%-5d", arry[i]);
    printf("\n");
    Half_Insert_Sort(arry, LEN);
    for (i = 0; i < LEN; ++i)
        printf("%-5d", arry[i]);
    printf("\n");
    
    return 0;
}

void Half_Insert_Sort(int * arr, int n)
{
    int i, j, temp;
    int low, mid, high;
    for (i = 1; i < n; ++i)
    {
        temp = arr[i];
        for (low = 0, high = i - 1; high >= low; )
        {
            mid = (low + high) / 2;
            if (temp < arr[mid])
                high = mid - 1;
            else
                low = mid + 1;
        }
        for (j = i-1; j >= low; --j)
            arr[j + 1] = arr[j];
        arr[low] = temp;
    }

    return;
}      
/* 
    冒泡排序
    原理是臨近的數字兩兩進行比較,按照從小到大或者從大到小的順序進行交換,
    這樣一趟過去後,最大或最小的數字被交換到了最後一位,
    然後再從頭開始進行兩兩比較交換,直到倒數第二位時結束,其餘類似看例子
    例子為從小到大排序
*/ 

# include <stdio.h>
# define LEN 6

void bubble_sort(int *, int);

int main(void)
{
    int arry[LEN] = {6, 2, 4, 1, 5, 9};
    int i;
    for (i = 0; i < LEN; ++i)
        printf("%-5d", arry[i]);
    printf("\n");
    bubble_sort(arry, LEN);
    for (i = 0; i < LEN; ++i)
        printf("%-5d", arry[i]);
    printf("\n");
    
    return 0;
}

void bubble_sort(int * arr, int len)
{
    int i, j;
    for (i = 0; i < len-1; ++i)
    {
        for (j = 0; j < len-1-i; ++j)
        {
            if (arr[j] > arr[j+1])
            {
                int temp;
                temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
        }
    }
    
    return;
}

/*
    Dve-C++
    - 輸出大小: 128.6396484375 KiB
    - 編譯時間: 1.75s
*/      
/*
    快速排序
    快速排序是對冒泡排序的一種改進。基本思想是：通過一趟排序後将
    需要排序的資料分割成獨立的兩部分，其中一部分的所有資料都比另
    外一部分的所有資料都要小，然後再按照此方法對這兩部分資料進行
    快速排序，整個排序過程可以遞歸進行，以此使整個資料都變成有序
    資料。 
*/

# include <stdio.h>
# define LEN 6

int quick(int *, int, int);
void sort(int *, int, int);

int main(void)
{
    int arry[LEN] = {6, 2, 4, 1, 5, 9};
    int i;
    for (i = 0; i < LEN; ++i)
        printf("%-5d", arry[i]);
    printf("\n");
    sort(arry, 0, LEN-1);
    for (i = 0; i < LEN; ++i)
        printf("%-5d", arry[i]);
    printf("\n");
    
    return 0;
}

int quick(int * arr, int low, int high)
{
    int key = 0;
    key = arr[low];
    while (low < high)
    {
        while (low < high && arr[high] >= key)
            --high;
        arr[low] = arr[high];
        while (low < high && arr[low] <= key)
            ++low;
        arr[high] = arr[low];
    }
    arr[low] = key;
    
    return low;
}

void sort(int * arr, int low, int high)
{
    if (low >= high)
        return;
    int aim = 0;
    aim = quick(arr, low, high);
    sort(arr, low, aim-1);
    sort(arr, aim+1, high);
    
    return;
}

/*
    Dve-C++
    - 輸出大小: 129.1630859375 KiB
    - 編譯時間: 0.34s
*/      
/*
    選擇排序
        簡單選擇排序的基本思想非常簡單,即:第一趟,從n個元素中找出關鍵字
        最小的元素與第一個元素交換;第二趟,在從第二個元素開始的n-1個元素
        中再選出關鍵字最小的元素與第二個元素交換;如此,第k趟,則從第k個元
        素開始的n-k+1個元素中選出關鍵字最小的元素與第k 個元素交換,直到整
        個序列按關鍵字有序?選擇排序是不穩定的排序方法
        在簡單選擇排序的基礎上,對其進行改進的算法有樹型選擇排序和堆排序
*/ 

# include <stdio.h>
# define LEN 6

void select_sort(int *, int);

int main(void)
{
    int arry[LEN] = {3, 7, 5, 9, 1, 4};
    int i;
    for (i = 0; i < LEN; ++i)
        printf("%-5d", arry[i]);
    printf("\n");
    select_sort(arry, LEN);
    for (i = 0; i < LEN; ++i)
        printf("%-5d", arry[i]);
    printf("\n");
    
    return 0;
}

void select_sort(int * arr, int len)
{
    int i, j;
    int min;          // 記錄最小數的下标 
    for (i = 0; i < len-1; ++i)
    {
        min = i;      //  假設此時下标為 i 的數最小 
        // 找出 a[i+1] 到 a[n] 之間的最小數，并将其下标用 min 記錄
        for (j = i+1; j < len; ++j)
        {
            if (arr[j] < arr[min])
                min = j;
        } 
        if (min != i)
        {
            int temp;
            temp = arr[i];
            arr[i] = arr[min];
            arr[min] = temp;
        }
    }
    
    return;
}

/*
    Dve-C++
    - 輸出大小: 128.6396484375 KiB
    - 編譯時間: 0.38s
*/      
/*
    插入排序 
        有一組資料，先取出第一個數，把它作為一個有序的數組。然後
        接着再取一個數，将它放到那個有序數組裡的一個合适位置，使
        得這個數組仍然有序。如此循環下去，每次從原數組中取出一個
        數，放到有序的數組裡 
*/

# include <stdio.h>
# define LEN 6

void insert_sort(int *, int);

int main(void)
{
    int arry[LEN] = {6, 2, 4, 1, 5, 9};
    int i;
    for (i = 0; i < LEN; ++i)
        printf("%-5d", arry[i]);
    printf("\n");
    insert_sort(arry, LEN);
    for (i = 0; i < LEN; ++i)
        printf("%-5d", arry[i]);
    printf("\n");
    
    return 0;
}

void insert_sort(int * arr, int len)
{
    int i, j, k, target;
    for (i = 0; i < len-1; ++i)
    {
        target = arr[i+1];
        for (j = i; j >= 0; --j)
        {
            if (target > arr[j])
                break;
        } 
        for (k = i+1; k > j+1; --k)
            arr[k] = arr[k-1];
        arr[j+1] = target;    
    }
    
    return;
}

/*
    Dve-C++
    - 輸出大小: 128.6396484375 KiB
    - 編譯時間: 0.41s 
*/      
/*
    shell排序
        從第一個元素開始，對間距為 h 的元素進行排序，排好後再從第
        二個元素與間隔為 h 的元素開始往後排，直到排到第 h 個元素，
        這樣就能保證所有元素都按間隔為 h 排了一遍，保證元素與間隔
        h 的元素之間是有序的。然後再按 h = (h-1)/3 不斷縮小 h 在
        排一遍，一點點縮小間隔到保證間隔為 1 的元素之間都是有序的。
        這樣較直接插入排序而言，減少了數組元素移動的次數。 
*/ 

# include <stdio.h>
# define LEN 6

// shell排序一遍
void shell_pass(int *, int, int);
void shell_sort(int *, int);

int main(void)
{
    int arry[LEN] = {6, 2, 4, 1, 5, 9};
    int i;
    for (i = 0; i < LEN; ++i)
        printf("%-5d", arry[i]);
    printf("\n");
    shell_sort(arry, LEN);
    for (i = 0; i < LEN; ++i)
        printf("%-5d", arry[i]);
    printf("\n");
    
    return 0;
}

// shell排序一遍，h 為目前增量
void shell_pass(int * arr, int h, int len)
{
    int i, j, key;
    for (i = h; i < len; ++i)  // 增量之後的所有記錄在自己所在的組進行插入排序 
    {
        key = arr[i];  // 目前記錄
        for (j = i-h; j >= 0 && arr[j] > key; j -= h)
            arr[j+h] = arr[j];
        arr[j+h] = key; 
    }
    
    return;
} 

void shell_sort(int * arr, int len)
{
    int h = len;
    do
    {
        h = h/3 + 1;  // 下一趟增量 
        shell_pass(arr, h, len);
    }while(h > 1); 
    
    return;
}
資料 直接插入排序 c++
上一篇: centos系統服務優化SHELL腳本
下一篇: 計算機組成原理寄存器初始化,計算機組成原理寄存器實驗

繼續閱讀