数据结构笔记9章

• 冒泡排序思路比较简单：

  1. 将序列当中的左右元素，依次比较，保证右边的元素始终大于左边的元素；
     （ 第一轮结束后，序列最后一个元素一定是当前序列的最大值；）
  2. 对序列当中剩下的n-1个元素再次执行步骤1。
  3. 对于长度为n的序列，一共需要执行n-1轮比较
     （利用while循环可以减少执行次数）

*代码实现

#冒泡排序 def bubble_sort(L):
    length = len(L) #序列长度为length，需要执行length-1轮交换 for x in range(1,length): #对于每一轮交换，都将序列当中的左右元素进行比较 #每轮交换当中，由于序列最后的元素一定是最大的，因此每轮循环到序列未排序的位置即可 for i in range(0,length-x): if L[i] > L[i+1]:
                temp = L[i]
                L[i] = L[i+1]
                L[i+1] = temp

• 快速排序的基本思想：挖坑填数+分治法
  1. 从序列当中选择一个基准数(pivot)
     在这里我们选择序列当中第一个数最为基准数
  2. 将序列当中的所有数依次遍历，比基准数大的位于其右侧，比基准数小的位于其左侧
  3. 重复步骤1.2，直到所有子集当中只有一个元素为止。
     用伪代码描述如下：
     1．i =L; j = R; 将基准数挖出形成第一个坑a[i]。
     2．j--由后向前找比它小的数，找到后挖出此数填前一个坑a[i]中。
     3．i++由前向后找比它大的数，找到后也挖出此数填到前一个坑a[j]中。
     4．再重复执行2，3二步，直到i==j，将基准数填入a[i]中
• 代码实现：

#快速排序 #L：待排序的序列；start排序的开始index,end序列末尾的index #对于长度为length的序列：start = 0;end = length-1 def quick_sort(L,start,end): if start < end:
        i , j , pivot = start , end , L[start] while i < j: #从右开始向左寻找第一个小于pivot的值 while (i < j) and (L[j] >= pivot):
                j = j-1 #将小于pivot的值移到左边 if (i < j):
                L[i] = L[j]
                i = i+1 #从左开始向右寻找第一个大于pivot的值 while (i < j) and (L[i] < pivot):
                i = i+1 #将大于pivot的值移到右边 if (i < j):
                L[j] = L[i]
                j = j-1 #循环结束后，说明 i=j，此时左边的值全都小于pivot,右边的值全都大于pivot #pivot的位置移动正确，那么此时只需对左右两侧的序列调用此函数进一步排序即可 #递归调用函数：依次对左侧序列：从0 ~ i-1//右侧序列：从i+1 ~ end
        L[i] = pivot #左侧序列继续排序
        quick_sort(L,start,i-1) #右侧序列继续排序
        quick_sort(L,i+1,end)

• 1. 归并排序是建立在归并操作上的一种有效的排序算法，该算法是采用分治法的一个典型的应用。它的基本操作是：将已有的子序列合并，达到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。
  2. 归并排序其实要做两件事：
  • 分解----将序列每次折半拆分
  • 合并----将划分后的序列段两两排序合并
    因此，归并排序实际上就是两个操作，拆分+合并
  1. 如何合并？
     L[first...mid]为第一段，L[mid+1...last]为第二段，并且两端已经有序，现在我们要将两端合成达到L[first...last]并且也有序。
  • 首先依次从第一段与第二段中取出元素比较，将较小的元素赋值给temp[]
  • 重复执行上一步，当某一段赋值结束，则将另一段剩下的元素赋值给temp[]
  • 此时将temp[]中的元素复制给L[]，则得到的L[first...last]有序
  1. 如何分解？
     在这里，我们采用递归的方法，首先将待排序列分成A,B两组；然后重复对A、B序列
     分组；直到分组后组内只有一个元素，此时我们认为组内所有元素有序，则分组结束。

• 代码实现

# 归并排序 #这是合并的函数 # 将序列L[first...mid]与序列L[mid+1...last]进行合并 def mergearray(L,first,mid,last,temp): #对i,j,k分别进行赋值
    i,j,k = first,mid+1,0 #当左右两边都有数时进行比较，取较小的数 while (i <= mid) and (j <= last): if L[i] <= L[j]:
            temp[k] = L[i]
            i = i+1
            k = k+1 else:
            temp[k] = L[j]
            j = j+1
            k = k+1 #如果左边序列还有数 while (i <= mid):
        temp[k] = L[i]
        i = i+1
        k = k+1 #如果右边序列还有数 while (j <= last):
        temp[k] = L[j]
        j = j+1
        k = k+1 #将temp当中该段有序元素赋值给L待排序列使之部分有序 for x in range(0,k):
        L[first+x] = temp[x] # 这是分组的函数 def merge_sort(L,first,last,temp): if first < last:
        mid = (int)((first + last) / 2) #使左边序列有序
        merge_sort(L,first,mid,temp) #使右边序列有序
        merge_sort(L,mid+1,last,temp) #将两个有序序列合并
        mergearray(L,first,mid,last,temp) # 归并排序的函数 def merge_sort_array(L): #声明一个长度为len(L)的空列表
    temp = len(L)*[None] #调用归并排序
    merge_sort(L,0,len(L)-1,temp) 

8、基数排序

• 1. 基数排序：通过序列中各个元素的值，对排序的N个元素进行若干趟的“分配”与“收集”来实现排序。
     分配：我们将L[i]中的元素取出，首先确定其个位上的数字，根据该数字分配到与之序号相同的桶中
     收集：当序列中所有的元素都分配到对应的桶中，再按照顺序依次将桶中的元素收集形成新的一个待排序列L[ ]
     对新形成的序列L[]重复执行分配和收集元素中的十位、百位...直到分配完该序列中的最高位，则排序结束
  2. 根据上述“基数排序”的展示，我们可以清楚的看到整个实现的过程
• 代码实现

#************************基数排序**************************** #确定排序的次数 #排序的顺序跟序列中最大数的位数相关 def radix_sort_nums(L):
    maxNum = L[0] #寻找序列中的最大数 for x in L: if maxNum < x:
            maxNum = x #确定序列中的最大元素的位数
    times = 0 while (maxNum > 0):
        maxNum = (int)(maxNum/10)
        times = times+1 return times #找到num从低到高第pos位的数据 def get_num_pos(num,pos): return ((int)(num/(10**(pos-1))))%10 #基数排序 def radix_sort(L):
    count = 10*[None] #存放各个桶的数据统计个数
    bucket = len(L)*[None] #暂时存放排序结果 #从低位到高位依次执行循环 for pos in range(1,radix_sort_nums(L)+1): #置空各个桶的数据统计 for x in range(0,10):
            count[x] = 0 #统计当前该位(个位，十位，百位....)的元素数目 for x in range(0,len(L)): #统计各个桶将要装进去的元素个数
            j = get_num_pos(int(L[x]),pos)
            count[j] = count[j]+1 #count[i]表示第i个桶的右边界索引 for x in range(1,10):
            count[x] = count[x] + count[x-1] #将数据依次装入桶中 for x in range(len(L)-1,-1,-1): #求出元素第K位的数字
            j = get_num_pos(L[x],pos) #放入对应的桶中，count[j]-1是第j个桶的右边界索引
            bucket[count[j]-1] = L[x] #对应桶的装入数据索引-1
            count[j] = count[j]-1 # 将已分配好的桶中数据再倒出来，此时已是对应当前位数有序的表 for x in range(0,len(L)):
            L[x] = bucket[x]