常用的排序算法(一)
常用的排序算法(一)
eatnothing 发表于2年前
常用的排序算法(一)
  • 发表于 2年前
  • 阅读 181
  • 收藏 3
  • 点赞 1
  • 评论 0

腾讯云 新注册用户 域名抢购1元起>>>   

摘要: 直接插入排序,快速排序,冒泡排序,冒泡排序的改进,简单选择排序

Date: 2016-02-14 #####排序算法的学习 ####冒泡排序

  • 时间复杂度:当顺序为正序的时候,为最好状态时间复杂度为O(N),平均时间复杂的为O(N^2)
  • 因为没有创建新的存储结构所以空间复杂度为O(1)
  • 冒泡排序是一种稳定的排序算法

#include <stdio.h>
void Bubble_sort(int A[],int n);

void Bubble_sort(int A[],int n){
    int i,j,temp;
    for(i= 0 ;i < n - 1 ;i++){
        for(j = 0;j< n -1 - i;j++){
            if(A[j] > A[j+1]){
                temp = A[j+1];
                A[j+1] = A[j];
                A[j] = temp;

            }

        }
    }

}

int main(int argc, const char * argv[]) {

    int A[7]={3,1,2,4,6,8,1};

    Bubble_sort(A, 7);

    for(int i =0; i < 7;i++){
        printf("%d",A[i]);

    }

}

####改进的冒泡排序

  • 使用冒泡排序对N个数据进行排序,一共需要进行n-1次比较,本来是正常顺序的数据也需要进行n-1次排序,所以当判断所有的数据为有序的时候不在进行排序直接跳出循环,
void Bubble_sort(int A[],int n){
    int i,j,temp,flag=0;
    for(i= 0 ;i < n - 1 ;i++){
        for(j = 0;j< n -1 - i;j++){
            if(A[j] > A[j+1]){
                temp = A[j+1];
                A[j+1] = A[j];
                A[j] = temp;
                flag = 1;

            }
        }
        if(flag== 0){
            break;
        }else{
            flag = 0;
        }
    }

}

####快速排序法

  • 算法时间复杂度:最差时间为(O(n^2))),平均时间复杂度为O(n*log2n)
  • 算法空间复杂度:O(log2n)~O(n)
  • 快速排序法是通过一遍排序将需要排序的数据分为两部分,使其中一部分数据比另一部分数据小,然后在分别对这两部分数据进行这种排序,直到每个部分为空或者只含有一个数的时候,排序结束
  • 快速排序是一种分治策略,将大批数据逐步分解,可以使用递归的方式便携程序

method: 变量left保存数组最小序号0,数组right保存数组最大(序号)长度n,在变量base 中保存A[0]为基准,从数组右侧开始逐个取出元素与base比较,如果小于base的值则将该数保存到A[left]中(A[0])元素中,接下来从数组左侧开始逐个取出元素与base比较知道找到比base大的数据,(left随着比较的位数自增),将这个比基准大的数存到A[right]中,接下来递归进行同样的操作

int Division(int a[],int left,int right){
    int base = a[left];     //取左侧元素为基准元素
    while(left<right){      //左侧元素的序号小于右侧
    while (left<right&&a[right]>base)  //当序号小于右侧并且数组末尾的值大于基准,则向前挪一位(right-1)
        --right;
        a[left] = a[right];         //当找到了右侧比基准小的数的时候令A[LEFT] 为右侧的值
    while(left<right&&a[left]<base)     //当序号小于右侧时候,如果左侧的数值比基准小则向后挪一位(left+1)
        ++left;
        a[right] = a[left];             //当找到左侧比基准大的数字的时候,让这个数字为数组的末尾元素()
        }
    a[left] = base;             //保存基准数
    return left;        //返回左侧的值
}

void QuickSort(int a[],int left,int right){

    int i, j;
    if(left<right){
        i = Division(a, left, right);
        QuickSort(a,left,i-1);  //左侧的数进行递归排序
        QuickSort(a,i+1,right);     //右侧的数进行递归排序
    }
}
int main(int argc, const char * argv[]) {
    // insert code here...
    int A[10]={94,84,54,80,62,83,37,24,67,29};

    QuickSort(A,0,9);

    for(int i = 0;i<10;i++){
        printf("%d",A[i]);
    }
    return 0;
}

####简单选择排序算法

  • 时间复杂度:O(n2)
  • 空间复杂的:O(1) method:对N个记录进行扫描,选择最小的记录,将其输出,接着在剩下的N-1个记录中扫描,选择最小的输出,不断重复这个过程,直到只剩一个记录为止
void selectSort(int A[],int n );

void selectSort(int A[],int n){
    int i,j,k,t;
    for(i = 0 ;i< n -1 ;i++){   //n-1位开始比较
        k = i;                  //获取当前位数
        for(j =i+1 ;j< n;j++){
            if(A[k]>A[j]){      //如果当前位数大于数组[K,N]的任何一位则,当前该数为[K,N]中最小的数
                k = j;
            }
        }
        t = A[i];       //进行交换
        A[i] =  A[k];
        A[k] = t;

    }
}
int main(int argc, const char * argv[]) {
    int A[8]={15,2,8,3,1,9,7,6};
    selectSort(A, 8);
    for(int i =0 ;i<8;i++){
        printf("%d",A[i]);
    }
}

####直接插入排序法

  • 时间复杂度:O(N^2)
  • 空间复杂度:O(1)
  • method:通过构建有序序列,对于未排序的数据,在已排序的序列中从后向前扫描,找到相应的位置并插入该数据,使数据形成有序队列
void insertSort(int A[],int n){
    int i,t,j;
    for(i = 1 ;i<n;i++){
        t= A[i];        //取出一个未排序的数据
        for(j=i-1;j>=0&&t<A[j];j--)     //在排序序列查找数据
            A[j+1] = A[j];              //向后移动数据
        A[j+1] = t;
    }

}
int main(int argc, const char * argv[]) {
    // insert code here...

    int A[6]={3,1,8,3,2,5};
    insertSort(A, 6);
    for(int i =0 ;i<6;i++){
        printf("%d",A[i]);
    }
    printf("Hello, World!\n");
    return 0;
}

共有 人打赏支持
粉丝 37
博文 128
码字总数 68736
×
eatnothing
如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!
* 金额(元)
¥1 ¥5 ¥10 ¥20 其他金额
打赏人
留言
* 支付类型
微信扫码支付
打赏金额:
已支付成功
打赏金额: