基础数据结构与算法7：简单排序算法

0.测试框架

• 创建随机数数组void Create_RandomArr(int* arr,int n){}

// 产生随机数数组
// 随机产生 0~n-1 之间的随机数
void Create_RandomArr(int* arr,int n){
        srand(time(NULL));
        for(int i=0;i<n;i++){
                arr[i] = rand()%n;
        }
}

• 判断数组是否有序bool Judge_order(int* arr,int n,bool flag){}

// 判断数组是否有序
// true 默认升序 false 默认降序
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;
}

• 函数：交换两个数void swap(int* a,int* b){}

// 交换两个数
void swap(int* a,int* b){
        int temp = *a;
        *a = *b;
        *b = temp;
}

• 函数：打印数组void PrintArr(int* arr,int n){}

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

• qsort()函数的回调函数int cmp(const void* a,const void* b){}

// qsort()回调函数
int cmp(const void* a,const void* b){
        return *(int*)a - *(int*) b;
}

1.冒泡排序法

1.1 方法

依次比较相邻两个元素的大小，进行排序。

冒泡排序过程

• 特殊情况：有序数组
  对冒泡排序进行优化：如果在一次冒泡排序过程中，没有进行过元素交换，则不再进行接下来的遍历。

1.2 实现

1.实现一次冒泡排序

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 已经是有序的序列 不需要在进行遍历
        return order;
}

2.实现多次冒泡排序

• 递归形式

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 复杂度

• 时间复杂度
  n-1+n-2+n-3+...+1 = (n-1+1)*(n-1)/2 = O(n²)
• 空间复杂度 O(1)

2.选择排序

2.1 方法

首先进行一次遍历，找到最大元素的下标，然后将最大元素与最后一个元素交换。

选择排序过程

2.2 实现

1.遍历找到该数组最大元素的下标

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.实现多次找到的最大元素与尾元素进行交换

• 递归形式

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 复杂度

• 时间复杂度 O(n²)
• 空间复杂度 O(1)

3.插入排序

3.1 方法

不断将元素插入到有序数组中。

• 从前向后遍历

  
  
  插入排序过程

• 从后向前遍历

  
  
  插入排序过程2

3.2 实现

1.将数据插入到一个有序数组中

• 从前向后遍历

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.依次在数组中插入数字
每次执行insert()或者insert2()后得到的都是有序数组

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

3.3 复杂度

• 时间复杂度 O(n²)
• 空间复杂度 O(1)

4.比较