学习目标插入排序快速排序计算机语言发展历史(一)程序设计语言的发展经历了机器语言、汇编语言、高级语言三个阶段。第一代计算机语言称为机器语言。计算机只能识别o和1。机器语言就是0/1组成的序列。机器语言是计算机唯一能够直接识别并执行的语言,但不易学习和修改,且不同类型机器的机器语言不同,只适合专业人员使用,现在几乎已经没有人用机器语言直接编程了。插入排序● 类比抓牌,打牌时一边抓牌一边按花色和大小插入到恰当的位置,当抓完所有的牌时,手中的牌便是有序的,这排序方法即为插入排序● 也可以类比插队,其他人已经按身高排好队了,新来的人要根据自己的身高找到合适位置插队● 插入排序的基本思想:每次将下一个元素插入到已排序序列中正确的位置插入排序的主要步骤如下:(升序为例)总共n-1趟(1 = i = n-1)第i趟,需要将第i+1个元素插入到前i个元素组成的有序序列中。①将第i+1个元素存放在临时变量t中②把第j个元素和t的值进行比较(j从i递减到1,逆向)③如果第j个元素的值t,则将该元素后移一个位置④否则,找到插入位置为j+1,将t的值放在j+1位置插入排序的核心代码:(升序)for(inti=1;i=n-1;i++){intt=a[i+1];intj=i;while(j=1a[j]t){a[j+1]=a[j];//a[j]的值后移到j+1j--;// 指针前移}//循环终止说明已找到插入位置a[j+1]=t;// 插入}其中循环可以用for循环for(j=i;j=1;j--){if(a[j]t)a[j+1]=a[j];elsebreak;}· 时间复杂度为O(n2)· 需要额外的空间来存储当前元素·插入排序是稳定的排序插入排序是稳定的排序例如,初始序列(2,2,1):221-221-1 22第1趟,第二个2不大于第一个2,所以没有发生后移和插入,两个2的顺序没有发生变化。而后面即便有其他的元素的插入,也不会使已排序的元素的前后顺序发生颠倒,所以插入排序是稳定的排序!为什么冒泡排序、选择排序和插入排序都需要O(n2)的时间?因为理论上任意两个不同元素都需要比较,共n(n-1)/2次。是否可以减少比较次数?有没有快一点的比较排序法?·由C.A.R.Hoare在1960年提出· 也是基于比较的排序方法· 平均时间复杂度为O(n log n)· 是比较快速的排序方法快速排序快速排序的基本思想:● 采用分治的策略,将一个大序列分成两个小序列,然后递归地对这两个小序列进行排序。● 其核心在于选择一个基准值(pivot),通过一趟排序将待排序列分割成独立的两部分,左边的子序列中是所有 = 基准值的数,右边部分是所有=基准值的数,且子序列内部不保证有序:【 = 基准值的数 …… 】【=基准值的数.】● 继续对两个子序列进行排序,直到全部有序单趟快排:选基准值并分区什么是对数快速排序-扩展排序算法比较·n为待排序元素的数量· 稳定性仅针对本课中该算法的实现方式而言给定num组数据(1num = 100),每组数据包含一个长度n(0n = 10000)和n个整数组成的序列。要求用快速排序法把这些序列的数从小到大排序,然后输出,每组一行。【输入】多行。第一行为数字num,其后是num组数据。每组由两行组成:第一行为长度n,第二行为n个整数,数之间空格隔开。【输出】n行。每行是对应的升序排序后的数,数之间空格隔开。【输入样例】1105 4 9 7 6 2 1 3 8 -1【输出样例】-1 1 2 3 4 5 6 7 8 91. 声明qsort函数voidqsort(inta[],intstart,intend