排序-选择排序

发表于

简单选择排序

简单的排序处理流程
(1)从待排序序列中，找到关键字最小的元素;
(2)如果最小元素不是待排序序列的第一个元素，将其和第一个元素互换;
(3)从余下的N-1个元素中，找出关键字最小的元素，重复(1)、(2)步，直到排序结束。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public void selectionSort(int[] list){
    //需要遍历获得最小值得次数
    //注意一点，当排序N个数，经历N-1次遍历，排序完成
    for( int i=0; i<list.length; i++){
        int temp = 0;
        int index = i; // 用来保存最小值的索引
        for( int j=i+1; j<list.length; j++){
            if(list[index]>list[j]){
                index = j;
            }
        }
        temp = list[index];
        list[index] = list[i];
        list[i] = temp;
    }
    return list;
}

堆排序

二叉堆是完全二叉树或者是近似完全二叉树。
二叉堆满足两个特性:
1、父节点的键值总是大于或等于(小于或等于)任何一个子节点的键值。
2、每个结点的左子树和右子树

1
2
3
4
5
6
7
8
9
10
11
12
def heap_adjust(data, s, m):
    if 2*s > m:
        return
    temp = s - 1
    if data[2*s-1] > data[temp]:
        temp = 2*s - 1
    
    if 2*s <= m-1 and data[2*s] > data[temp]:
        temp = 2*s
    if temp<> s-1: