本章内容

两种最基本数据结构——数组与链表。以及优缺点。
学习简单的选择排序算法。

小结

计算机内存犹如大抽屉。
需要存储多个元素时，采用数组或链表。
数组的元素都在一起。
链表的元素分开，其中每个元素都存储了下一个元素的地址。
数组的读取速度很快。
链表的插入和删除速度很快。
在同一个数组中，所有元素的类型都必须相同。

2.1 内存的工作原理

看电影

寄存

柜子 》 抽屉 》雨伞

电影座位

数组 ： 预定5个连座。插入不方便，遍历方便
链表 ： 5人分开坐。插入方便，遍历不方便。

数组支持随机访问

• 有两种访问方式：随机访问和顺序访问。其中链表只支持顺序访问。

  2.3 简单选择排序

• 随着推进，需要检查的元素数越来越少

• 第一次检查n个，第二次检查n-1个，，，2个，1个
• O(n)

python实现

def

# 先编写一个用于找出数组中最小值的函数
def findSmallest(arr):
    smallest = arr[0]
    smallest_index = 0
    for i in range(1,len(arr)):
        if arr[i] < smallest:
            smallest = arr[i]
            smallest_index = i
    return smallest_index
# 简单选择排序
def selectionSort(arr):
    newArr = []
    for i in range(len(arr)):
        smallest_index = findSmallest(arr) 
        newArr.append(arr.pop(smallest_index))   //弹出已排序元素，并将其入栈新数组
    return newArr

call

C实现

选择排序

def

// 两元素交换
void swap(int *a,int *b){
    int tmp;
    tmp = *a;
    *a = *b;
    *b = tmp;
}
// 选择排序
void selection_sort(int arr[],int len){
    int i,j,small_index;
    for(i=0;i<len-1;i++){  
        //其实，这里i也可以取到len-1,因为，嵌套中的j=len虽然越界，但是还有j<len的循环条件。
        small_index = i;
        for(j=i+1;j<len;j++){
            if(arr[j] < arr[small_index])
                small_index = j; //记录最小元素所在索引
        }
        swap(&arr[i],&arr[small_index]);
    }
}

call

#include<stdio.h>
#include "..\love\selection_sort.h"
int main(){
    int arr[5] = {4,3,1,5,8};
    int len=5,i;
    selection_sort(arr,len);
    for(i=0;i<len;i++)
        printf("%d ",arr[i]);
    return 0;
}