排序算法.md

各种排序算法

#include <stdio.h>
#include <limits.h>
#include <stdlib.h>
/* 冒泡排序 */
void bubbleSort(int *arr, int length){
    int i ,j;
    for(i = length - 1 ; i >=0 ; i--){
        for(j = 0;j < i ; j++){
            if(arr[j+1] < arr[j]){
                int tmp = arr[j+1];
                arr[j+1] = arr[j];
                arr[j] = tmp;
            }
        }
    }
    //打印一下结果
    for(i = 0 ; i < length ; i ++){
        printf("Array's %d element is %d \n", i, arr[i]);
    }
}
/* 插入排序 */
void insertSort(int* arr, int length){
    int i,j;
    for(i= 1 ; i< length; i++){
        for(j = i;j >= 1 ; j--){
            if(arr[j]>= arr[j-1]){
                break;
            }else{
                sweep_element(arr,j, j-1);
            }
        }
    }
    for (i = 0; i < length; i++)
    {
        printf("Array's %d element is %d \n", i, arr[i]);
    }
}
/* 选择排序 : 每一次遍历选择一个最大的*/
void selectSort(int* arr, int length){  
    int i,j;
    int min;
    int min_flag;
    for(i = 0 ; i < length ; i++){
        min_flag = i;
        min=arr[i];
        for(j = i ; j < length ; j++){
            if(arr[j] < min){
                min = arr[j];
                min_flag = j;
            }
        }
        sweep_element(arr, i, min_flag);
    }
    for (i = 0; i < length; i++)
    {
        printf("Array's %d element is %d \n", i, arr[i]);
    }
}
/* 快速排序 */
int *quickSort(int *arr, int start, int end)
{
    /* 分治法实现 */
    if( start >= end){
        return ;
        //结束条件
    }
    int flag = start - 1;
    /* 随机中间数 */
    int pivot = rand() % (end - start + 1) + start;
    int pivot_ele = arr[pivot];
    sweep_element(arr,pivot,end);
    for(int i = start;i < end;i++){
        if(arr[i] < pivot_ele){
            flag++;
            sweep_element(arr,flag,i);
        }
    }
    flag++;
    sweep_element(arr,flag, end);
    quickSort(arr,start, flag-1);
    quickSort(arr,flag+1,end);
    return arr; 
}

void sweep_element(int *arr, int i, int j) {
    if(i == j) {
        return ;
    }
    int flag = i - 1;

    int tmp = arr[i];
    arr[i] = arr[j];
    arr[j] = tmp;
}

int main(){
    int test[] = {11,2,54,34,454,78,0};
    int length  = sizeof(test) / sizeof(test[0]);
    int *result= quickSort(test, 0, length);
    for (int i = 0; i < length; i++)
    {
        printf("Array's %d element is %d \n", i, result[i]);
    }
    return 0;
}

刷题

数组去重

int * removeDuplicates(int *nums, int numsSize) {
    int i = 0;
    int max = nums[numsSize - 1];
    // 这里作数组交换处理
    while( i < numsSize) {
        if(nums[i] == max) {
            break;
        }
        if(i+1 < numsSize && nums[i+1] == nums[i] ) {
            //交换
            for(int j = i+1 ;j + 1 < numsSize ; j++){
                int temp = nums[j+1];
                nums[j+1] = nums[j];
                nums[j] = temp;
            }
        }else{
            i++;
        }
    }
    return nums;
}