直接选择排序
首先在未排序序列中找到最小(大)元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小(大)元素，然后放到已排序序列的末尾。实际适用的场合非常罕见。
void selection_sort(int arr[], int len) {
int i, j, min, temp;
for (i = 0; i < len - 1; i++) {
min = i;
for (j = i + 1; j < len; j++)
if (arr[min] > arr[j])
min = j;
temp = arr[min];
arr[min] = arr[i];
arr[i] = temp;
}
}
堆排序
堆排序利用了大根堆(或小根堆)堆顶记录的关键字最大（或最小）这一特征，使得在当前无序区中选取最大（或最小）关键字的记录变得简单。
- 先将初始文件R[1...n]建成一个大根堆，此堆为初始的无序区。
- 再将关键字最大的记录R[1]（即堆顶）和无序区的最后一个记录R[n]交换，由此得到新的无序区R[1...n-1]和有序区R[n],且满足R[1...n-1].key <= R[n].key。
- 由于交换后新的根R[1]可能违反堆性质，故应将当前无序区R[1...n-1]调整为堆。然后再次将R[1...n-1]中关键字最大记录R[1]和该区间的最后一个记录R[n-1]交换，由此得到新的无序区R[1...n-2]和有序区R[n-1...n],且仍满足关系R[1...n-2].key <= R[n-1].key,同样要将R[1...n-2]调整为堆。
- 直到无序区只有一个元素为止。
static void max_heap(int[] num, int start, int end) {
int dad = start;
int son = dad * 2 + 1;
while (son < end) {
if (son + 1 < end && num[son] < num[son + 1])
son++;
if (num[dad] > num[son])
return;
else {
num[dad] ^= num[son];
num[son] ^= num[dad];
num[dad] ^= num[son];
dad = son;
son = dad * 2 + 1;
}
}
}
static void heap_sort(int[] num) {
for (int i = num.length / 2 - 1; i >= 0; --i) {
max_heap(num, i, num.length);
}
for (int i = num.length - 1; i >= 0; --i) {
num[i] ^= num[0];
num[0] ^= num[i];
num[i] ^= num[0];
max_heap(num, 0, i);
}
}
