排序算法——冒泡排序、快速排序、选择排序

时间：2021-09-14 22:08:08

一、冒泡排序：

思想：
  每次比较相邻的元素，顺序不对就交换。如果按从大到小排序，后面的数比前面的数大，则交换两个数。一直比较下去直到最后两个数比较完为止，每一趟找出一个最小或者最大的值放在一边，每一趟需要比较的次数为n-i （i为第几趟）。
  用两个for循环，外层for循环是要比的趟数(n-1)。内层for循环是用来遍历数组，依次比较相邻两个数。

时间复杂度：两个for循环相乘，(n-1)*(n-1) =O(n^2)

排序算法——冒泡排序、快速排序、选择排序

void bubble(int a[],char str)
{
int i,j;
int temp;

if(str == '>')
    {
for(i = 1;i <= N-1;i++ )   //跑的趟数
        {
for(j = 1;j <= N-i;j++ )  //相邻两个数比较的次数
            {
if(a[j-1] < a[j])  
                {   //交换数据
                    temp=a[j-1];
                    a[j-1]=a[j];
                    a[j]=temp;
                }
            }
        }
    }


else if(str == '<' )
    {
for(i = 1;i <= N-1;i++ )
        {   
for(j = 1;j <= N-i;j++ )
            {   
if(a[j-1] > a[j])
                {   
                    temp=a[j-1];
                    a[j-1]=a[j];
                    a[j]=temp;
                }
            }
        } 
    }

}

int main()
{
    printf("please input five number:\n");

int i;
int a[N];
char str;

for(i = 0;i< N;i++)
    {
        scanf("%d",&a[i]);
    }
    getchar();  //读取缓冲区的换行符\n，否则下面str接收到额字符就会是\n

//输入从小到大还是从大到小
    printf("please input a list rank: < or >?"); 

str=getchar();  

    bubble(a,str);

for(i=0;i<N;i++)
    {
        printf("%d ",a[i]);
    }

}

对于上诉读入一个字符来判断是从大到小还是从小到大。也可以用字符串的形式来读取：

具体格式：

char str[5];
scanf("%s",&str);
bubble(a,str);

函数参数也需要修改:
bubble(int a[ ],char *str) 或者bubble(int a[ ],char str[ ])

然后判断需要用strcmp函数判断两个字符串是否相等：
strcmp(str，”<” ) == 0

二、快速排序：

思想：
首先找一个基准数，然后从左右两头开始找（右边先开始），在相遇之前，对于从小到大的顺序来说：右边找到一个数大于该基准书，左边小于该基准书，就交换两个数。一直到他们相遇为止，因为是右边先移动，所以最后时那个数如果小于基准数，就把基准数与该数进行交换。到最后要到达的效果就是：以该基准数为界，比他小的放在左边，比他大的放在右边。也就是二分的思想，不断进行二分，二分法退出成立条件：前面的数大于后面的数。

排序算法——冒泡排序、快速排序、选择排序

快速排序——从小到大排序代码：

#include <stdio.h>
int a[10]={6,1,2,7,9,3,4,5,10,8};

void quick_sort(int left,int right)
{
int t,temp;
int i,j;   
if(left > right)     //退出判断机制，二分法结束的标志就是前一个数大于后一个数
    {
return;
    }

    temp=a[left];   //保存基准数

//分别把letf和right赋给i 和 j
    i=left;
    j=right;

while(i != j)
    {
if(a[j] >= temp && i<j) //j先从又向左找大于基准数的数
            j--;


if(a[i] <= temp && i<j) //i从左往右找小于基准数的数
            i++;


//找到一个大于基准数，一个小于基准数，两者交换
if(i < j)
        {
            t=a[j];
            a[j]=a[i];
            a[i]=t;
        }

    }

//一直到i=j后，做如下处理：

//把基准数放在临界位置，与a[left]交换数据
    a[left]=a[i];
    a[i]=temp;

//递归调用，每次前半部分的right改变，后半部分的left改变。
    quick_sort(left,i-1);
    quick_sort(i+1,right);
}

void main()
{
int i;

    quick_sort(0,9);   //invoking

for(i=0; i<10; i++)
    {
printf("%d ",a[i]);
    }
    getchar();

}

开始运行的时候没有输出结果，因为没有加上递归时候的二分法的退出机制，所以程序一直卡在递归函数中。后面加了一个判断：left>right后就可以正常退出了。

三、选择排序：

思想：
  在要排序的一组数中，选出最小（或者最大）的一个数与第1个位置的数交换；然后在剩下的数当中再找最小（或者最大）的与第2个位置的数交换，依次类推，直到第n-1个元素（倒数第二个数）和第n个元素（最后一个数）比较为止。

  要找到最小值所在数组的下标，然后把该下标对应的数组与依次与a[0] a[1] ….交换数据。值得一提的是，排序每循环依次，需要把 i 的传给SelectMinKey（）函数作为它循环的起始值，目的是为了不再把已经放好的数组再拿出来比较，否则没有啥意义。

选择排序——从小到大：

#include <stdio.h>
int i;

//找出最小的值。
int SelectMinKey(int a[], int n, int x)    
{      
int j=0;
int k = x;      //x是for循环i传过来的值，目的是不再比较前面已经放好的数组的位置。
for(j=x+1 ;j< n; ++j) 
    {          
if(a[k] > a[j]) 
        k =j;      
    }      
return k;   //返回最小值的下标
} 


void selectSort(int a[], int n)
{  
int key, tmp;  
for(i = 0; i< n; ++i) 
    {  
        key = SelectMinKey(a, n,i);           
if(key != i)   //依次交换最小值与前排序号的数据
        {  
            tmp = a[i];  
            a[i] = a[key]; 
            a[key] = tmp; 
        }  
    }  
} 

int main()
{ 
int i; 
int a[8] = {3,1,5,7,2,4,9,6};  

    selectSort(a, 8);  

for(i=0 ;i < 8 ; i++ )
    {
printf("%d ",a[i]);
    }   
}




标签：

相关文章