查找与排序-选择排序

选择排序也是基于“比较”和“交换”两种操作来实现的排序方法。

每一趟排序在待排序序列中选择关键字最小（或最大）的数据元素加入到排好序的序列前（或后），直至所有元素排完为止。

一、简单选择排序

1.简单选择排序基本思想

也称直接选择排序。假设待排序的n个数据元素存放在数组a中，那么简单选择排序可做如下描述：（1）第一趟从a[0]开始，通过n-1次比较，从n个数据元素中选出最小元素，记为a[min]，与a[0]交换；

（2）依次类推，第i趟从a[i-1]开始，通过n-i次比较，从n-i+1个元素中找出最小元素，记为a[min]，与a[i-1]交换；

（3）经过n-1趟排序，算法结束。

2.简单选择排序举例

例：设待排元素序列为{56,25,70,99,82,10,15,56}，请给出简单选择排序法进行排序的过程。

3.简单选择排序算法代码

def selection_sort(self):
    for i in range(0, len(self.data)-1):
        min = i
        for j in range(i + 1, len(self.data)):
          if self.data[min].key > self.data[j].key:
              min = j
        self.data[min], self.data[i] = self.data[i], self.data[min]

def selection_sort(self):
    for i in range(0, len(self.data)-1):
        min = i
        for j in range(i + 1, len(self.data)):
            if self.data[min].key > self.data[j].key:
                min = j
        if min != i:
            self.data[min], self.data[i] = self.data[i], self.data[min]

4.简单选择排序算法分析

（1）空间复杂度：只在交换的时候需要辅助空间，所以空间复杂度为O(1)。

（2）时间复杂度：该算法在寻找每趟的最小元素的时候，每一趟需要比较（n-i）次，每次最多做3次移动。

总的比较次数为

总的移动次数为

因此时间复杂度为O(n2).

（3）该算法是不稳定算法。

二、堆排序

1.堆排序的基本概念

堆的概念：

①如果每个非叶结点值都大于或者等于其孩子结点值，称为大顶堆。

②如果每个非叶结点值都小于或者等于其孩子结点值，称为小顶堆。

堆排序把待排序序列中的数据元素看成一棵完全二叉树，利用完全二叉树中双亲结点和孩子结点之间的内在关系，在当前无序的序列中选择关键字最大或最小的记录。

2.大顶堆排序的基本思想

方法步骤：

（1）对待排序列数组a进行建堆操作得到大顶堆。

（2）对a[n-1]和堆顶元素a[0]进行交换操作，从而使得a[n-1]为最大元素。

（3）将剩下的子序列a[0]到a[n-2]进行调整操作，使得子序列也为大顶堆，然后对a[n-2]和a[0]进行交换操作，从而使得a[n-2]为次大元素。

（4）以此类推，直到最后交换了a[1]和a[0]，得到非递减有序序列，算法结束。

利用堆排序需要解决两个问题：

（1）如何将n个元素的序列按关键字建成堆；

（2）输出堆顶元素后，怎样调整剩余元素，使其成为一个新大顶堆。

3.堆排序举例

例：将数据元素序列{56,25,10,99,82,70,15,56}用大顶堆方法排序。

4.堆排序代码

def heap_sort(self):
    data_len = len(self.data)
    #从最后一个非叶结点开始，将每个非叶结点为根的子树部分调整成堆
        for i in range(data_len // 2 - 1, -1, -1):
        self.sift_down(i, data_len - 1)
    for j in range(data_len-1, 0, -1):
        # 堆顶与j号元素交换
                self.data[0], self.data[j] = self.data[j], self.data[0]
        # 将序列中0号至j-1号部分调整成堆
                self.sift_down(0, j - 1)

def sift_down(self, i, end):
    temp = self.data[i]
    j = 2 * i + 1
    while j <= end:
        if j < end and self.data[j].key < self.data[j + 1].key:
            j = j + 1
        if temp.key > self.data[j].key:
            break
        else:
            self.data[i] = self.data[j]
            i = j
            j = 2 * j + 1
    self.data[i] = temp