2017-10-18

大话数据结构读书笔记(一)——冒泡排序

准备工作

1.指针与结构体

参考网址: http://www.cnblogs.com/qyaizs/articles/2039101.html

指向结构体类型变量的使用

定义结构体：
struct stu{
    char name[20];
    long number;
    float score[4];
};
//再定义指向结构体类型变量的指针变量
struct stu *p1, *p2;
//定义指针变量p1、p2，分别指向结构体类型变量。
引用形式为：指针变量→成员;
或者是指针变量.成员
typedef struct{
    char name[20];
    long number;
    float score[4];
}Stu;
//typedef(type define)在这里的作用是为结构体起了一个名为Stu的别名，当我们再次定义变量的时候，就可以直接使用Stu来定义了。

2.i++

i++ 返回原来的值，++i 返回加1后的值。
i++ 不能作为左值，而++i 可以。
3. Status
typedef int status;

C语言中没有status这个关键字.但一般写程序时,会定义这样的一个类型,用来表示成功或失败状态.如：0表示成功,-1表示失败。这样status就可以定义成int类型,然后用它去定义变量或函数返回值类型。其实上面也已经提到过，typedef有重命名的意思，也就是说这一句话也可以表示又重新定义了一个变量表示int这种数据类型，然后这种数据类型可以专门用来表示状态。

4.malloc函数的用法

须要包括头文件：#include ‘stdlib.h’
函数声明(函数原型)：void *malloc(int size);
malloc 向系统申请分配指定size个字节的内存空间。返回类型是 void 类型。void 表示未确定类型的指针
void* 类型能够强制转换为不论什么其他类型的指针
我们必须手动指定分配的空间的大小

int TR=(int)malloc(L->length sizeof(int));/ 申请额外空间 */

1 2	(分配类型)malloc(分配元素个数sizeof(分配类型)) + 此处的分配类型是为了将原来的void*类型强制转换为我们需要定义成的类型。

5.一些基础准备

内排和外排
根据排序过程中待排序的记录是否全都放置在内存中。如果是则是内排序，否则由于排序的记录太多，不能同时放置在内存，整个排序过程需要在内外存之间多次交换数据，这样的排序称为外排序。
稳定性，⚠️是否稳定由排序算法决定。假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，ri=rj，且ri在rj之前，而在排序后的序列中，ri仍在rj之前，则称这种排序算法是稳定的；否则称为不稳定的。

线性表的顺序存储结构

#define MAXSIZE 10///* 用于要排序数组个数最大值，可根据需要修改 */
typedef struct {
    int r[MAXSIZE +1];/* 用于存储要排序数组，r[0]用作哨兵或临时变量 */
    int length;/* 用于记录顺序表的长度 */
}SqList;

swap函数

/* 交换L中数组r的下标为i和j的值 */
void swap(SqList *L,int i,int j) { 
    int temp=L->r[i]; 
    L->r[i]=L->r[j]; 
    L->r[j]=temp; 
}

2.冒泡排序(以递增为例)

依次比较相邻两个数据的大小，如果右边的数据比左边的数据小，那么交换两个数的位置，我想叫冒泡排序的原因就是因为本来大的数从原本队列中冒出到前面。

c语言版

⚠️⚠️⚠️在方法二和方法三中，j的条件是j>=
i,这样做的目的是在每次循环遍历排序的时候，最小值已经冒泡到了最前端，i的值也在不断变化着，所以j并不需要对i左边的数据进行比较和排序。
方法一并不满足冒泡排序的思想，只是简单的两两交换，虽然达到了排序的目的，但是效率低下。

void BubbleSort0(SqList * L){
    int i, j;
    for (int i = 1; i < L->length; ++i){
        for (int j = i+1; j <= L->length; j++){
            if (L->r[i]>L->r[j]){
                swap(L, i, j);
            }
        }
    }
}
//对于一个数组下标为1-9，那么i的指针依次从1走到8，而j的指针呢，则是从2走到9

方法二冒泡排序最后的小数据不断的网上冒，直到走到适合他的位置。

void BubbleSort1(SqList * L){
    int i, j;
    for (int i = 1; i < L->length; ++i){
        for (int j = L->length-1; j>=i; j--){
            if (L->r[j+1]>L->r[j]){
                swap(L, i, j);
            }
        }
    }
}

方法三，改进的冒泡排序，增加了对数组某些数据是否已经有序的判断。避免对已经有序的数据进行遍历比较，增加不必要的时间消耗。

void BubbleSort2(SqList * L){
    int i, j;
    Status flag = true;
    for (int i = 1; i < L->length && flag; ++i){
        for (int j = L->length-1; j>=i; j--){
            flag = false;
            if (L->r[j+1]>L->r[j]){
                swap(L, i, j);
                flag = true;
            }
        }
    }
}

时间复杂度分析

最好情况：需要排序的数据已经是一个有序的，故只需要遍历一次就可以确定这是一个排序完成的序列，此时时间复杂度为O(n)
最坏情况：需要排序的数据恰好是一个反序列的数据，所有的数据都需要进行一次循环遍历排序，此时的时间复杂度为1+2+..+(n-1)=(n-1)(n-1+1)/2=n(n-1)/2
综上所述，时间复杂度为O(n^2)

本文标题:大话数据结构读书笔记(一)——冒泡排序

文章作者:Gentlelynn

发布时间:2017-10-18, 19:14:12

最后更新:2018-03-16, 19:19:13

原始链接:https://gentlelynn.github.io/2017/10/18/20180110data1/

许可协议: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。