0.測試框架

• 創(chuàng)建隨機數(shù)數(shù)組void Create_RandomArr(int* arr,int n){}

// 產(chǎn)生隨機數(shù)數(shù)組
// 隨機產(chǎn)生 0~n-1 之間的隨機數(shù)
void Create_RandomArr(int* arr,int n){
        srand(time(NULL));
        for(int i=0;i<n;i++){
                arr[i] = rand()%n;
        }
}

• 判斷數(shù)組是否有序bool Judge_order(int* arr,int n,bool flag){}

// 判斷數(shù)組是否有序
// true 默認(rèn)升序 false 默認(rèn)降序
bool Judge_order(int* arr,int n,bool flag){
        for(int i=0;i<n-1;i++){
                if(flag){
                        if(arr[i] > arr[i+1]) return false;
                }else{
                        if(arr[i] < arr[i+1]) return false;
                }
        }
        return true;
}

• 函數(shù)：交換兩個數(shù)void swap(int* a,int* b){}

// 交換兩個數(shù)
void swap(int* a,int* b){
        int temp = *a;
        *a = *b;
        *b = temp;
}

• 函數(shù)：打印數(shù)組void PrintArr(int* arr,int n){}

// 打印數(shù)組
void PrintArr(int* arr,int n){
        for(int i=0;i<n;i++){
                printf("%d ",arr[i]);
        }
        printf("\n");
}

• qsort()函數(shù)的回調(diào)函數(shù)int cmp(const void* a,const void* b){}

// qsort()回調(diào)函數(shù)
int cmp(const void* a,const void* b){
        return *(int*)a - *(int*) b;
}

1.冒泡排序法

1.1 方法

依次比較相鄰兩個元素的大小，進行排序。

冒泡排序過程

• 特殊情況：有序數(shù)組
  對冒泡排序進行優(yōu)化：如果在一次冒泡排序過程中，沒有進行過元素交換，則不再進行接下來的遍歷。

1.2 實現(xiàn)

1.實現(xiàn)一次冒泡排序

bool bubble(int* arr,int n){
        bool order = true;
        for(int i=0;i<n-1;i++){
                if(arr[i] > arr[i+1]){
                        swap(arr+i,arr+i+1);
                        order = false;
                }
        }
        // 沒有交換的情況下 order = true 已經(jīng)是有序的序列 不需要在進行遍歷
        return order;
}

2.實現(xiàn)多次冒泡排序

• 遞歸形式

void Bubble_sorting(int* arr,int n){
        if(n>0){
                bubble(arr,n);
                Bubble_sorting(arr,n-1);
        }
}

• 迭代形式

void Bubble_sorting2(int* arr,int n){
        for(int i=n;i>0;i--){
                bubble(arr,i);
        }
}

1.3 復(fù)雜度

• 時間復(fù)雜度
  n-1+n-2+n-3+...+1 = (n-1+1)*(n-1)/2 = O(n²)
• 空間復(fù)雜度 O(1)

2.選擇排序

2.1 方法

首先進行一次遍歷，找到最大元素的下標(biāo)，然后將最大元素與最后一個元素交換。

選擇排序過程

2.2 實現(xiàn)

1.遍歷找到該數(shù)組最大元素的下標(biāo)

int Find_max(int* arr,int n){
        int index_max = 0;
        for(int i=0;i<n;i++){
                if(arr[index_max]  < arr[i]){
                        index_max = i;
                }
        }
        return index_max;
}

2.實現(xiàn)多次找到的最大元素與尾元素進行交換

• 遞歸形式

void Select_sorting(int* arr,int n){
        if(n>0){
                int index_max = Find_max(arr,n);
                swap(arr+index_max,arr+n-1);
                Select_sorting(arr,n-1);
        }
}

• 迭代形式

void Select_sorting2(int* arr,int n){
        for(int i=0;i<n;i++){
                int index_max = Find_max(arr,n-i);
                swap(arr+index_max,arr+n-1-i);
        }
}

2.3 復(fù)雜度

• 時間復(fù)雜度 O(n²)
• 空間復(fù)雜度 O(1)

3.插入排序

3.1 方法

不斷將元素插入到有序數(shù)組中。

• 從前向后遍歷

  
  
  插入排序過程

• 從后向前遍歷

  
  
  插入排序過程2

3.2 實現(xiàn)

1.將數(shù)據(jù)插入到一個有序數(shù)組中

• 從前向后遍歷

void insert(int* arr,int n){
        // 確定要插入的元素(最后一個元素)
        int insert_data = arr[n-1];

        for(int i=0;i<n-1;i++){
                if(arr[i] > insert_data){
                        memmove(arr+i+1,arr+i,(n-i-1)*sizeof(int));
                        arr[i] = insert_data;
                        break;
                }
        }
}

• 從后向前遍歷

void insert2(int* arr,int n){
        int insert_data = arr[n-1];
        for(int i=n-2;i>=0;i--){
                if(insert_data < arr[i]){
                        arr[i+1] = arr[i];
                }else{
                        arr[i+1] = insert_data;
                        return;
                }
        }
        // 如果一直不return,則最后arr[0] = insert_data;
        arr[0] = insert_data;
}

2.依次在數(shù)組中插入數(shù)字
每次執(zhí)行insert()或者insert2()后得到的都是有序數(shù)組

void Insert_sorting(int* arr,int n){
        for(int i=1;i<=n;i++){
                // insert(arr,i);
                insert2(arr,i);
        }
}

3.3 復(fù)雜度

• 時間復(fù)雜度 O(n²)
• 空間復(fù)雜度 O(1)

4.比較