当前位置:   article > 正文

排序方法之交换排序(C语言实现)_编程实现交换排序函数并在main()中调用c语言

编程实现交换排序函数并在main()中调用c语言

小白学习排序记录

 (二)交换排序

1.冒泡排序

数组data[n];

中心代码:二重循环

具体实现:相邻的两个数依次比较,若data[i]>data[i+1],则交换数值,每比较一趟,就有一个数有序,最后一个数不用比,将数组排好序后,总比较趟数为n-1次,每一趟的比较次数不同,列出每一趟的比较次数(k),都有i(比较趟数)+k(每一趟的比较次数)=n(总的数据个数)
代码

int findKLargest(int* nums, int numsSize, int k)//在一个无序的数组中查找第k大的数

{

int data=0, flag=1;//date用于暂时存储数据,flag用于判断内循环是否进行了交换,若没有进行,说明前面是已经有序的,不用再排前面的

int n=numsSize;

for(int i=0;i<=n-1&&flag==1;i++)//进行n-1趟

{

        flag=0;

        for(int j=1;j<n-i;j++)//每一趟比较次数为n-i

            {

                if(nums[j]>nums[j+1])//前比后大就就交换

                {

                        data=nums[j];

                        nums[j]=nums[j+1];

                         nums[j+1]=data; flag=1;

                }

            }

}

return nums[numsSize-k+1];

}

PS:这个方法的时间复杂度是O(n*n)空间复杂度是O(1),并不是最好的。

最小的时间复杂度是O(n)。

这个只是我练习的记录。

2.快速排序

中心代码:递归+循环

具体实现:(注意我是用线性表写的)在线性表中找一个界点pivot,可以任意定线性表中某一个位置的数字为pivot,我这里使用了一个函数从两头查找(单向比较浪费时间),找的过程中将让线性表中每一个数与pivot比较,小的放pivot前面,大的放pivot后面,用于找到pivot大概排序好后位于线性表哪个位置,将表分为两个子表,并且返回此时pivot的下标,再重复上方的步骤,直到子表中只有一个数字后,证明线性表已经排完了。(每进行一次查找界点位置,就把界点排好了)
代码

int partition(L &l, int low, int high)//判断中间的那个数 
{
    l.data[0]=l.data[low];
//线性表中0号位置没有装数值,选择第一个数为界点
    //存在0号位置方便后续直接存入相应的下标位置 

    int pivotkey=l.data[low];//将界点的值传给一个整数方便后续比较 
        while(low<high)//当low与high重合的时候证明线性表已经查找完
        //此时high和low的下标就是界点排好序后大概位于的位置 
        {
            while(low<high&&l.data[high]>=pivotkey)--high;
//
从后面开始找,当high所指的值比界点小就进行下一步,否则--high 
            //已经将界点的数值存入了0号位置,0号位置相当于空了,此时需要从后面找一个比界点小的数存入1号位置 

            l.data[low]=l.data[high]; 
            while(low<high&&l.data[low]<=pivotkey)++low;
/
/从前面开始找,当low所指的值比界点大就进行下一步,否则++low 
            l.data[high]=l.data[low];
        }
     l.data[low]=l.data[0];
//
将0号位置保存的界点值。存入此时low的位置 
     return low;
//返回low的下标值作为分开线性表的标准 
}
void Sqsort(L &l, int low, int high)
{
    int pivot;
    if(low<high)
/
/用于判断该线性表不是只有一个数字或者为空 
    //和判断子表是否只有一个数值了,子表中只有一个数字时,证明已经排完了
 
    {
        pivot=partition(l, low, high);

        Sqsort(l, low, pivot-1);//
将线性表分为两个子表分别递归再次重复上面的操作 
        Sqsort(l, pivot+1, high);
    }
}

PS:这个不是最简便的写快速排序的方法有更简单的

这个的时间复杂度是O(nlogn),空间复杂度是O(nlogn)。

总代码

#include<stdio.h>
#define maxsize 20
typedef struct Sqlist{
    int data[maxsize];
    int length;
}L;
void creatlist(L* l)
{
    l->length=0;
    int datament;
    printf("请输入你要排序的数字,n的个数小于20\n");
    int n;
    scanf("%d", &n);
    for(int i=1;i<=n;i++)
    {
        
        scanf("%d", &datament);
        l->data[i]=datament;
        l->length++;
    }
}

int partition(L &l, int low, int high)//判断中间的那个数 
{
    l.data[0]=l.data[low];//线性表中0号位置没有装数值,选择第一个数为界点
    //存在0号位置方便后续直接存入相应的下标位置 
    int pivotkey=l.data[low];//将界点的值传给一个整数方便后续比较 
        while(low<high)//当low与high重合的时候证明线性表已经查找完
        //此时high和low的下标就是界点排好序后大概位于的位置 
        {
            while(low<high&&l.data[high]>=pivotkey)--high;//从后面开始找,当high所指的值比界点小就进行下一步,否则--high 
            //已经将界点的数值存入了0号位置,0号位置相当于空了,此时需要从后面找一个比界点小的数存入1号位置 
            l.data[low]=l.data[high]; 
            while(low<high&&l.data[low]<=pivotkey)++low;;//从前面开始找,当low所指的值比界点大就进行下一步,否则++low 
            l.data[high]=l.data[low];
        }
     l.data[low]=l.data[0];//将0号位置保存的界点值。存入此时low的位置 
     return low;//返回low的下标值作为分开线性表的标准 
}
void Sqsort(L &l, int low, int high)
{
    int pivot;
    if(low<high)//用于判断该线性表不是只有一个数字或者为空 
    //和判断子表是否只有一个数值了,子表中只有一个数字时,证明已经排完了 
    {
        pivot=partition(l, low, high);
        Sqsort(l, low, pivot-1);//将线性表分为两个子表分别递归再次重复上面的操作 
        Sqsort(l, pivot+1, high);
    }
}
int main()
{
    L l;
    creatlist(&l);
    L &p=l;
    int m=l.length;
    printf("%d...\n", l.data[1]);
    printf("长度:%d\n", l.length );
    int low=1, high=m;
    Sqsort(p, low, high);
    while(m--)
    {
        printf("排好后的list:%d\n", l.data[m+1]); 
    }
    return 0; 
}

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/知新_RL/article/detail/806034
推荐阅读
相关标签
  

闽ICP备14008679号