八种排序算法实现和优化方案_C

布满荆棘的人生 2022-05-29 10:38 93阅读 0赞

# 一、插入排序 #

插入排序的排序原理就决定了它的适用于以下两种场景：

*  所排序的数据量比较小
 *  所排序的序列接近有序

空间复杂度：O(1)  
最优时间复杂度：O(N)  
最差时间复杂度：O(N^2)

void InsertSort(int *array, int size)
    {
        for (int i=1; i < size; i++)
        {
            int end = i-1;
            int key = array[i];
            while (end >= 0 && key < array[end])
            {
                array[end + 1] = array[end];
                end -= 1;
            }
            array[end + 1] = key;
        }
    }

**原版的插入排序在前面寻找插入元素的时候采用的方案是遍历查找，既然是查找，我们就可以用一个更加优化的查找方案来替换原来的遍历查找，这里我采用二分查找来优化**

void Insert_sort_pro(int *array, int size)
    {
        for (int i = 1; i < size; i++)
        {
            int end = i - 1;
            int left = 0;
            int right = end;
            int key = array[i];
            while (left <= right)
            {
                int mid = left + ((right - left) >> 1);
                if (array[mid] < key)
                {
                    left = mid + 1;
                }
                else
                {
                    right = mid - 1;
                }
            }
            while (end > right)
            {
                array[end + 1] = array[end];
                end--;
            }
            array[right + 1] = key;
        }
    }

# 二、希尔排序 #

最优时间复杂度：O(N^1.3)  
最差时间复杂度：O(N^2)  
空间复杂度：O(1)

**希尔排序可以看作是直接插入排序的优化版本**  
适用场景：

*  数据量比较大
 *  数据排列比较杂乱

void ShellSort(int *array, int size)
    {
        int gap = size;
        while (gap > 1)//保证当gap等于1时只排序一次
        {
            gap = gap / 3 + 1;
            for (int i = gap; i < size; i++)
            {
                int end = i - gap;
                int key = array[i];
                while (end >= 0 && key < array[end])
                {
                    array[end + gap] = array[end];
                    end -= gap;
                }
                array[end + gap] = key;
            }
        }
    }

# 三、选择排序 #

空间复杂度：O(1)  
时间复杂度：O(N^2)

#define Size(n) (sizeof(n)/sizeof(n[0]))
    
    void select_sort(int *arr, int n)
    {
        int min_index = 0; 
        int i=0,j=0; 
        for (; i < n-1; i++)
        {
            min_index = i;//每次循环将最小值默认为i所处的位置 
            for (j = i + 1; j < n; j++)
            {
                if (arr[j] < arr[min_index])
                {
                    min_index = j;
                }
            }
            if (i != min_index)
            {
                int temp = arr[i];
                arr[i] = arr[min_index];
                arr[min_index] = temp;
            }
        }
    }

**由于每次循环都要查找出未排序元素中的最大/最小元素，既然如此，那么我们自然可以在每次循环的时候同时找到最大元素和最小元素，然后将最大元素和最小元素分别放到数组的两边，依次往中间缩小排序的范围即可**

void SelectSort_pro(int *array, int size)
    {
        int max_idx = 0,min_idx = 0;
        int j = 0, i = 0;
        int start_idx = 0;
        int end_idx = size - 1;
        while(start_idx < end_idx )
        {
            max_idx = min_idx = i;
            for (j = start_idx+1; j <= end_idx ; ++j)
            {
                if (array[max_idx] < array[j]){
                    max_idx = j;
                }
                if (array[min_idx] > array[j]){
                    min_idx = j;
                }
            }
            if (end_idx != max_idx)
                Swap(&array[end_idx], &array[max_idx]);
            if (array[min_idx]== array[end_idx] && start_idx != max_idx)
                Swap(&array[start], &array[max]);
            else if (start_idx != min_idx)
                Swap(&array[start_idx], &array[min_idx]);
            --end_idx;
            ++start_idx;
        }
    }

# 四、堆排序 #

空间复杂度：O(1)  
时间复杂度：O(Nlog N)

**实现代码：**

//辅助交换函数
    void Swap(int *data1,int *data2)
    {
        *data1 ^= *data2;
        *data2 ^= *data1;
        *data1 ^= *data2;
    }
    
    
    // 堆调整 向下调整 
    void HeapAdjust(int* array, int size, int parent)
    {
        int child=parent * 2 + 1;
        while(child < size)
        {
            if((child + 1 < size) && array[child+1] > array[child])
                child += 1;
            if(array[child] > array[parent])
            {
                Swap(&array[child],&array[parent]);
                parent=child;
                child = parent * 2 + 1;
            }
            else
                return;
        }
    }
    // 堆排序 
    void HeapSort(int* array, int size)； 
    {
        if(NULL == array)
            return;
        int parent=(size-2)>>1;
        for(; parent > 0; parent--)
        {
            HeapAdjust(array,size,parent);
        }
        int end = size-1;
        while(end > 0)
        {
            Swap(*array[0],&array[end]);
            HeapAdjust(array,end,0);
            --end;
        }
    }

# 五、冒泡排序 #

空间复杂度：O(1)  
最优时间复杂度：O(N)  
最差时间复杂度：O(N^2)

//辅助交换函数
    void swap(int *x,int *y)
    {
        *x=*x ^ *y;
        *y=*x ^ *y;
        *x=*x ^ *y;
    }
    void Bubble_sort(int *arr,int size)
    {
        int i=0;//外层循环变量 
        int j=0;//内层循环变量 
        for(;i < size-1;i++)
        {
            for(j=0;j < size-1-i;j++)
            {
                if(arr[j]>arr[j+1])
                    swap(&arr[j],&arr[j+1]);
            }
        }
    }

**若是在外层循环还没有走完的时候，当前序列已经有序，则不需要再接着走完循环，所以只要在执行一遍内层循环而没有交换任意元素，则说明当前序列已经有序，直接退出循环，优化代码如下：**

void Bubble_sort_pro(int arr[],int size)
    {
        int i=0;//外层循环变量 
        int j=0;//内层循环变量 
        int flag;//用于判断是否需要进行排序 
        for(;i < size-1;i++)
        {
            flag=0;
            for(j=0;j < size-1-i;j++)
            {
                if(arr[j]>arr[j+1])
                {
                    flag=1;
                    swap(&arr[j],&arr[j+1]);
                }   
            }
            if(!flag)
                break;
        }
    }

# 六、快速排序 #

最优时间复杂度O(log N）  
最差时间复杂度O(N^2)

最优空间复杂度O(log N)  
最差空间复杂度O(N)

**实现方法一：挖坑填数法（挖坑+分治）**

int _quick_sort_dig(int arr[],int low,int high)
    {
        int key;
        key=arr[low];
        while(low<high)
        {
            while(low < high && arr[high]>=key)
            {
                high--;
            }
            if(low<high)
            {
                arr[low++]=arr[high];
            }
            while(low < high && arr[low] <= key)
            {
                low++;
            }
            if(low < high)
            {
                arr[high--]=arr[low];
            }
         } 
         arr[low]=key;
         return low;
    }
    
    void quick_sort_dig(int arr[],int start,int end)
    {
        int pos;
        if(start<end)
        {
            pos=_quick_sort_dig(arr,start,end);
            quick_sort(arr,start,pos-1);
            quick_sort(arr,pos+1,end);
        }
    }

**实现方法二：hoare版快排（交换+分治）**

int _quick_sort_hoare(int *array,int left,int right)
    {
        right -= 1;
        int key=array[right];
        int end =right;
        while(left < right)
        {
            while(left < right && array[left] <= key)
            {
                left++;
            }
            while(left > right && array[right] >= key)
            {
                right--;
            }
            Swap(&array[left],&array[right];
        }
        if(left != end)
        {
            Swap(&array[end],&array[left]);
        }
        return left;
    }
    
    void quick_sort_hoare(int *array,int left,int right)
    {
        int mid=0;
        if(left < right)
        {
            mid=_quick_sort_hoare(array,left,right);
            quick_sort_hoare(array,left,mid);
            quick_sort_hoare(array,mid+1,right);
        }
    }

**上面的两种方法在一个地方采用的方式都是相同的，就是在选取每一次排序的比较元素时，都选取了最左边或者最右边的一个数字，这样做是方便，可是却有一个隐患，如果当前数组已经有序或者接近有序，那么每次取到的比较元素都是最大或者最小，则每次都要遍历数组才能找到目标位置，这样一来，快排的时间复杂度就退化到了O(N^2),为了解决这个问题，下面是一种优化方案：**

**实现方法3：双指针版快排+三数取中法**

//每次都在数组中随机选择三个数，最后取这三个数的中间数作为比较数字
    int Find_Mid(int *array,int left,int right)
    {
        int mid_idx= left +((right - left)>>1);//left mid right
        int mid_num=0;
        mid_num = array[left] < array[mid_idx] ? array[left] : array[mid_idx];
        if(mid_num == array[left])
            return mid_num < array[right] ? left : right;
        else
            return mid_num < array[right] ? mid_idx : right;
    }
    
    int _quick_sort_pro(int *array,int left,int right)
    {
        int cur=left;
        int mid=Find_Mid(array,left,right);//采用三数取中法
        if(mid != cur-1)
            Swap(&array[mid],&array[cur-1]);
        int prev=cur-1;
        while(cur < right)
        {
            if(array[cur] < key && ++prev != cur)
            {
                Swap(&array[cur],&array[prev]);
            }
            cur++;
        }
        if(++prev != size)
        {
            Swap(array[prev],array[size-1]);
        }
        return prev;
    }
    
    void quick_sort_pro(int *array,int left,int right)
    {
        int mid=0;
        if(left < right)
        {
            mid=_quick_sort_pro(array,left,right);
            quick_sort_pro(array,left,mid);
            quick_sort_pro(array,mid+1,right);
        }
    }

**实现方法4：迭代式快排**

> 这里直接调用栈的接口，测试的时候要包含栈的头文件

void quick_sort_Nor(int *array,int size)
    {
        int left=0;
        int right=size;
        int mid=0;
        Stack _stack;
        InitStack(&_stack);
        StackPush(&_stack,right);
        StackPush(&_stack,left);
        while(!StackEmpty(&_stack))
        {
            left=StackTop(&_stack);
            StackPop(&_stack);
            right=StackTop(&_stack);
            StackPop(&_stack);
            mid=_quick_sort_best(array,left,right);
            if(left < right)
            {
                StackPush(&_stack,right);
                StackPush(&_stack,mid);
                StackPush(&_stack,mid);
                StackPush(&_stack,left);
            }
        }
    }

# 七、归并排序 #

空间复杂度：O（N）  
时间复杂度：O(N \* logN)

**递归版归并排序**

void Merge_Data(int *array,int mid,int left,int right,int *temp)
    {
        int begin1=left;
        int end1=mid;
        //因为我分区的区间是左闭右开区间，所以右半部分的起始要从上一个的结束标志开始
        int begin2=mid;
        int end2=right;
        int index=left;
        while(begin1 < end1 && begin2 < end2)
        {
            if(array[left] <= array[right])
            {
                array[index++]=array[left++];
            }
            else
            {
                array[index++]=array[right++];
            }
        }
        while(begin1 < end1)
        {
            array[index++]=array[left++];
        }
        while(begin2 < end2)
        {
            array[index++]=array[right++];
        }
    }
    void _Merge_sort(int *array,int left,int right,int *temp)
    {
        if(left < right)
        {
            int mid=left+(right-left)>>1;
            _Merge_sort(array,left,mid,temp);
            _Merge_sort(array,mind,right,temp);
            Merge_Data(array,mid,left,right,temp);
            memcpy(array+left,temp+left,sizeof(array[0])*(right - left));//如果上面归并的子函数中index是从0开始，则这里temp不需要加left
        }
    }
    //由于归并排序需要借助辅助空间，为了不在归并的时候反复进行空间的申请和释放，所以
    //封装一层函数，只在最上层的函数里申请一次空间，然后作为参数传到下层的函数即可
    void Merge_sort(int *array,int size)
    {
        int *temp=(int *)malloc(sizoef(array[0]) * size);
        Merge_sort(array,0,size,temp);
    }

**迭代式归并排序**

void Merge_sort_Nor(int *array,int size)
    {
        int gap=1;
        int *temp=(int *)malloc(sizoef(array[0]*size);
        while(gap < size)
        {
            int left,mid,right;
            int i=0;
            for(i=0;i < size;i += 2 * gap)
            {
                left += gap;
                mid += gap;
                if(mid > size){
                    mid=size;
                }
                right += gap;
                if(right > size){
                    right=size;
                }
                Merge_Data(array,mid,left,right,temp);
            }
            //每一次归并完成后将已经归并的新元素集合拷贝到源数据集合中
            memcpy(array,temp,size * sizeof(array[0]));
            gap *= 2;
        }
        free(temp);
    }

# 八、计数排序 #

**1>基础版计数排序**  
数据个数：N  
数据范围：M  
空间复杂度：O(M)  
时间复杂度：O(N)

void Count_sort(int *array,int size)
    {
        int max_idx=array[0];
        int min_idx=array[0];
        int i=1;
        int index=0;
        int Space_size;
        int *tmp=NULL;
        for(;i < size;++i)//循环了N次
        {
            if(max_idx < array[i])
                max_idx=array[i];
            if(min_idx > array[i])
                min_idx=array[i];
        }
        Space_size=max_idx-min_idx + 1;//由数据范围确定分配的辅助空间大小
        tmp=(int *)malloc(sizoef(int) * Space_size);
        if(NULL == tmp){
            return;
        }
        memset(tmp,0,sizeof(int)*Space_size);//初始化辅助空间
    
        for(i=0;i < size;++i)//数据统计（循环了N次）
        {
            tmp[array[i]-min_idx]++;
        }
        for(i=0;i < Space_size; ++i)//数据回收(回收了N次）
        {
            while(tmp[i]--)
            {
                array[index++]=i + min_idx;
            }
        }
    }

--------------------

**2>基数排序（多关键码排序）**  
数据的位数：M  
数据个数：N  
空间复杂度：O(N)  
时间复杂度：O(M+N)

1.低关键码排序（MSD）  
**排序思路**：

1.将数据按照个位放到对应的桶中
    
    2.按照桶的编号对数据进行回收
    
    3.将数据拷贝回原来的空间
    
    4.将数据按照十位放到对应的桶中
    
    5.按照桶的编号对数据进行回收
        ……………………
    n.排序成功

**实现代码：**

int Get_bit(int *array, int size)
    {
        int count = 0;
        int i = 0;
        int index = 1;
        for (i = 0; i < size; i++)
        {
            while (array[i] <= index)
            {
                count++;
                index *= 10;
            }
        }
    }
    void Base_sort_LSD(int *array,int size)
    {
        int indx=1;
        int i=0;
        int bit=Get_bit(array,size);
        int *temp=(int *)malloc(sizoef(int)*size);
        while(bit > 0)
        {
            int addr[10]={
       0};
            int Count[10]={
       0};
            while(i < size)
            {
                Count[array[i] / indx % 10]++;
            }
            for(i =1;i < size;i++)
            {
                addr[i]=addr[i-1]+Count[i-1];
            }
            for(i=0;i < size;i++)
            {
                temp(addr[array[i] / indx % 10]++]=array[i];
            }
            memcpy(array,temp,sizeof(int)*size);
            bit--;
            indx += 10;
        }
    }