基础数据结构和算法6：简单排序算法

0. 测试框架

#include <stdio.h>
void print_array(int arr[],int n){
    for(int i=0;i<n;++i){
        printf("%d ",arr[i]);
    }
    printf("\n");
}
int* scanf_array(int arr[],int n){
    for(int i=0;i<n;++i){
        scanf("%d",&arr[i]);
    }
    return arr;
}
void swap(int* a,int* b){
    int temp = *a;
    *a = *b;
    *b = temp;
}

int main(){
    int n;
    scanf("%d",&n);
    int arr[n];
    scanf_array(arr,n);
    sort(arr,n);
    print_array(arr,n);
}

或者

// 生成n个数据的随机数列[1,100]
int* createRandArray(int n){
    int* arr = malloc(n*sizeof(int));
    srand(time(NULL));
    for(int i=0;i<n;++i){
        arr[i] = rand()%100+1;
    }
    return arr;
}
// 打印数组
void printArray(int* arr,int n){
    for(int i=0;i<n;++i){
        printf("%d ",arr[i]);
    }
    printf("\n");
}
// 判度数组是否是非递减排序
bool isOrder(int* arr,int n){
    for(int i=1;i<n;++i){
        if(arr[i]>=arr[i-1]){
            continue;
        }else{
            return false;
        }
    }
    return true;
}

测试OJ

• 牛课网：排序
• 51nod：排序

1. 冒泡排序

1.1 步骤

1. 首先实现一趟冒泡

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

2. 再实现多趟冒泡

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

1.2 参考代码

void bubble(int arr[],int n){
    for(int i=0;i<n-1;++i){
        if(arr[i] > arr[i+1]){
            swap(arr+i,arr+i+1);
        }
    }
}
void bubble_sort(int arr[],int n){
    for(int i=n;i>1;i--){
        bubble(arr,i);
    }
    // while(n>1) bubble(arr,n--);
}

1.3 时间复杂度

一共比较次，即

1.4 空间复杂度

随着的增长，排序不需要增加额外空间，空间复杂度为。

1.5 优化

尝试对已排序的数列冒泡排序

---

2. 选择排序

2.1 步骤

1. 首先实现一趟,找出最大数字的下标

   int find_max_index(int arr[],int n);
   

2. 实现多趟将最大数字与最后数字交换

   int selection_sort(int arr[],int n);
   

2.2 参考代码

int find_max_index(int arr[],int n){
    int max = arr[0];
    int max_index = 0;
    for(int i=1;i<n;++i){
        if(max < arr[i]){
            max = arr[i];
            max_index = i;
        }
    }
    return max_index;
}
void selection_sort(int arr[],int n){
    for(int i=n;i>1;--i){
        int max_index = find_max_index(arr,i);
        swap(arr+max_index,arr+i-1);// i是数组长度，最后一个元素下标要减1
    }
}

2.3 时间复杂度

一共比较次，即

2.4 空间复杂度

随着的增长，排序不需要增加额外空间，空间复杂度为。

2.5 优化

同时选择最大值和最小值

---

3. 插入排序

3.1 步骤

1. 实现向有序数列插入一个数字

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

2. 依次在数组中插入数字

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

3.2 参考代码

void insert(int arr[],int n){
    for(int i=n-2;i>=0;--i){
        if(arr[i+1]<arr[i]){
            swap(arr+i+1,arr+i);
        }
    }
}
void insertion_sort(int arr[],int n){
    for(int i=2;i<=n;++i){
        insert(arr,i);
    }
}

3.3 时间复杂度

一共比较次，即

3.4 空间复杂度

随着的增长，排序不需要增加额外空间，空间复杂度为。

3.5 优化

用移动代替交换

void insert(int arr[],int n){ // 最后一个元素是待插入元素
    int key=arr[n-1];
    int i=0;
    for(i=n-1;i>=1&&arr[i-1]>key;--i){
        arr[i] = arr[i-1];
    }
    arr[i] = key;
}

void insertion_sort(int arr[],int n){
    for(int i=1;i<n;++i){// 插入元素i操作
        insert(arr,i+1); // i+1表示数组长度，最后一个元素表示要插入的
    }
}

---

4. 分析

试一下下面的数据比较次数和交换次数

1. 随机
2. 正序
3. 逆序

5. 提高

1. 使用swap()和cmp()替换排序函数中的交换和比较处理。
2. 实现向qsort一样的排序函数。
   例如：

   void bubble_sort(void* arr[],int n,int size,int (*cmp)(const void*,const void*));
   

6. 小结

• 排序的稳定性
  在待排序的序列中，存在多个相同的关键字记录，经过排序这些记录相对位置保持不变，则这种排序称为稳定的，否则称为不稳定的。

No.	算法	Algorithm	Time Complexity	Space Complexity	Stable
1	冒泡排序	Bubble Sort			Yes
2	插入排序	Insertion Sort			Yes
3	选择排序	Selection Sort			No