选择类排序的基本思想是每一趟在n-(i-1)个待排序的记录中选取一个关键字最小的记录作为有序序列中的第i个记录。常用的选择类排序法有简单选择排序和堆排序。

1.简单选择排序

简单选择排序是对选择类排序基本思想的直接实现。在第一趟排序中，从第一个记录开始在待排序的n个记录中选择一个最小的记录，并和第一个记录作交换；在第二趟排序中，从第二个记录开始从待排序的n-1个记录中选择一个最小的记录，并和第二个记录做交换。依次类推，第i趟排序过程即从第i个元素开始在待排序的n-(i-1)个元素中选择一个最小的记录，并和第i个记录作交换。

void selectSort(int *r, int length)
{
	int i, j, k, n;

	n = length;

	for ( i = 1; i <= n - 1; i++) {
		k = i;

		for ( j = i + 1; j <= n; j++)
			if (r[j] < r[k])
				k = j;
		if ( k != i) {
			r[0] = r[i];
			r[i] = r[k];
			r[k] = r[0];
		}
	output(r, length);
	}
}

在具体实现时，外部循环用来控制总的排序趟数，而内部循环用于在剩余待排序记录中挑选一个最小的记录。在每一趟排序中，使用k记录最小记录的索引。

2.堆排序

堆排序将一维的待排序记录按照完全二叉树的形式进行组织，并利用完全二叉树中父节点和孩子节点之间的关系来选择记录，最终达到排序的目的。堆排序只是利用了完全二叉树的特性，待排序记录仍然采用一维数组进行存储，而非采用树的存储结构。 堆排序的算法思想是将待排序的记录r[1,n]看作是一棵完全二叉树，将记录1作为完全二叉树的根节点，记录中的其他元素依次逐层从左至右顺序排序。首先将该完全二叉树调整为大根堆（最终排列成递减序列），也就是创建堆的过程；接着，将根元素从二叉树中移除并作为有序记录集合中的第一个元素，同时再次调整该二叉树让其形成另一个大根堆。不断重复上述过程直到该完全二叉树为空。实现代码如下：

void heapSort(int *r, int length)
{
	int i, n;
	int t;

	create_heap(r, length);

	n = length;

	for ( i = n; i >= 2; i--) {
		t = r[1];
		r[1] = r[i];
		r[i]= t;
		adjust_heap(r, 1, i - 1);
		output(r, length);
	}
}

在具体的实现堆排序时，通常是将堆顶元素和堆尾元素进行交换，再次调整剩余待排序的元素形成堆。第i趟排序是将堆顶元素r[1]和堆尾元素r[n-i+1]进行交换，此时序列r中后i个元素是有序的。

堆的创建就是自底向上逐层调整该完全二叉树的子树。对于n个元素的记录来说，先将以第n/2个元素为根的子树调整为大根堆，再将以n/2-1个元素为根的子树调整为大根堆，按照逐层自底向上的顺序，直到根节点。

void create_heap(int *r, int length)
{
	int i, n;

	n = length;

	for ( i = n / 2; i >= 1; i--)
		adjust_heap(r, i, n);
}

整个堆排序的核心算法是调整堆，其中r[k,m]是一个以k元素为根的完全二叉树，该算法将此二叉树调整为堆。具体实现时，用r[0]备份当前二叉树的根元素，用j表示i元素的左孩子。算法中使用循环不断将二叉树调整为堆，它首先确定i节点的两个孩子中的较大值，再进一步判断是否需要与根节点进行交换。如果根节点大于i节点较大的那个孩子节点j，整个调整过程结束，因为此时该二叉树就是一个堆。否则将这个较大值的孩子j移到节点i处，接下来以j为根节点继续如上考察它的两个孩子节点的大小。

void adjust_heap(int *r, int k, int m)
{
	int i, j, t;
	int finished;

	r[0] = r[k];
	i = k;
	j = 2 * i;

	finished = 0;

	while (j <= m && !finished) {
		if (j < m && r[j] < r[j + 1])
			j++;
		if (r[0] >= r[j])
			finished = 1;
		else {
			r[i] = r[j];
			i = j;
			j = 2 * i;
		}
	}

	r[i] = r[0];
}

整个调整堆的过程是由根节点逐步向下筛选的过程。

交换类排序的基本思想是通过交换逆序元素而最终达到所有元素有序，这里的逆序是个广义概念，如果按照降序排序，那么前小后大的相邻元素就为逆序。常见的交换类排序方法有冒泡排序和快速排序。

1.冒泡排序

冒泡排序法的思想比较简单，依次扫描待排序的序列，并且从第一个元素开始比较相邻两个元素之间的大小，如果逆序则交换。假如有一个记录序列r[1,length]，以升序为例，在第i趟排序过程中需要对前length-(i-1)个元素进行逆序交换，最终这些记录中的最大元素将被交换到序列中第length-(i-1)这个位置上。

void bubbleSort(int *r, int length)
{
	int n, change;
	int i, j, k;

	n = length;
	change = 1;

	for ( i = 1; i <= n - 1 && change; i++) {
		change = 0;
		for ( j = 1; j <= n - i; j++)
			if (r[j] > r[j + 1]) {
				r[0] = r[j];
				r[j] = r[j + 1];
				r[j + 1] = r[0];
				change = 1;
			}
		output(r, length);
	}
}

对于n个元素的序列来说，整个冒泡排序最多进行n-1趟。这里还特别的增加了一个标志位change，只要做了逆序交换change就为真，如果某一趟中没有做任何交换，说明序列已经有序，则change为假，此时整个排序可以提前停止。

2.快速排序

冒泡算法中对相邻元素的交换一次只能消除一个逆序，如果通过交换两个不相邻的元素能一次消除多个逆序，则会增加整个排序的速度。快速排序就是基于这样的目的，在一次交换中可以消除多个逆序。

快速排序的基本思想是在待排序记录中选择一个记录作为标准，将大于该标准的所有元素移到该标准之后，将小于该标准的所有元素移到该标准之前。最终将待排序的记录分成两个子序列，而标准元素插入到两个子序列之间，上述过程为一趟快速排序过程。接下来再对两个子序列进行快速排序，不断的分割子表，直到子表长度不超过1为止，此时所有的记录都是有序的。

根据上述分析，可以通过递归来实现快速排序法。quickPass()用于一趟快速排序，并且返回标准元素的位置pos。

void quickSort(int *r, int low, int high, int length)
{
	int pos;


	if (low < high) {
		pos = quickPass(r, low, high);
		quickSort(r, low, pos - 1, length);
		quickSort(r, pos + 1, high, length);
		output(r, length);
	}
}

quickPass()用于实现一趟快速排序，一趟快速排序结束的条件是low不小于high。可以看到快速排序中是将low和high两个不相邻位置的元素进行交换。

int quickPass(int *r, int left, int right) 
{
	int low, high;

	low = left;
	high = right;
	r[0] = r[low];

	while (low < high) {
		while (low < high && r[high] >= r[0])
			high--;
		if (low < high) {
			r[low] = r[high];
			low++;
		}

		while (low < high && r[low] <= r[0])
			low++;
		if (low < high) {
			r[high] = r[low];
			high--;
		}
	}

	r[low] = r[0];
	return low;
}

这里也用到了r[0]，用它来存储标准元素，当一趟快速排序完成后，将标准元素插入low所指位置。

插入类排序的基本思路是在一个已经排好序的子记录上，每一步将下一个待排序的记录插入到已经排好序的记录子集中，直到将所有待排序记录全部插入为止。

1.直接插入排序

直接插入排序是最基本的插入排序算法，它的一趟操作是将第i个记录插入到前面i-1个已经排好序的记录中，在查找记录i的插入位置时，也在进行元素的移动。假设有一个待排序队列r[1,length]，则整个排序过程需要n-1次趟。直接插入算法的实现如下：

void insSort(int *r, int length)
{
	int i, j;

	printf("Sorting:\n");
	for ( i = 2; i <= length; i++) {
		r[0] = r[i];
		j = i - 1;

		while (r[0] < r[j]) {
			r[j + 1] = r[j];
			j--;
		}

		r[j + 1] = r[0];

		output(r, length);
	}
}

具体实现时，用一维数组来存储待排序的序列，其中0号元素备份待插入的记录。

2.折半插入排序

折半插入排序法与直接插入法类似，区别在于确定元素i插入的位置时利用折半查找法。每一趟排序的过程是先用折半查找法确定插入位置，再逐个进行元素的移动。

void binSort(int *r, int length)
{
	int i, j;
	int low ,high, mid;

	printf("Sorting:\n");
	for ( i = 2; i <= length; i++) {
		r[0] = r[i];
		low = 1;
		high = i - 1;

		while (low <= high) {
			mid = (low + high) / 2;
			if (r[0] < r[mid])
				high = mid - 1;
			else
				low = mid + 1;
		}

		for (j = i - 1; j >= low; j--) 
			r[j + 1] = r[j];
		r[high + 1] = r[0];
		output(r, length);

	}
}

与直接插入法类似，数组r中的0号元素也备份了待插入的元素i。当确定了记录i的位置时，此时存在low=high+1这样的关系，接下来将low到i-1之间的元素都后移一位，最终记录i刚好插入空出来的位置中。

3.希尔排序

整个希尔排序的过程由若干次希尔插入组成，具体次数由增量数组delta中的元素个数n确定。在每一次的希尔插入算法中，将待排序的记录序列分成d个稀疏子序列，每个稀疏子序列中元素之间的间隔正好为d。希尔插入算法就是将每一个子序列都按照直接插入法排列成有序，从而使得整个序列基本有序。上述过程会重复n次，就是希尔排序算法的整个过程。

void shellSort(int *r, int length, int *delta, int n)
{
	int i;
	for ( i = 0; i < n; i++) {
		shellInsert(r, length, delta[i]);
	}
}

第i趟希尔排序中，每个稀疏子序列中元素的间隔由delta[i]决定。但希尔算法的最后一趟排序，元素的间隔必需是1。因为最后一次希尔排序就相当于直接插入排序，但是此时整个记录序列已经几乎有序，因此移动的次数会大大减少。

void shellInsert(int *r, int length, int d)
{
	int i, j;
	int k;
	
	for (i = 1 + d; i <= length; i++) {
		if (r[i] < r[i - d]) {
			r[0] = r[i];
			
			for (j = i - d; j > 0 && r[0] < r[j]; j -= d) {
				r[j + d] = r[j];
			}
			r[j + d] = r[0];
		}
	}
	output(r, length);
}

虽然希尔插入算法中需要依次将d个子序列排成有序，但是实际的实现过程却从第一个子序列的第二个记录(d+1)开始依次遍历整个序列，因为每个序列中的元素都是由间隔d控制的，因此就相当于每个子序列各自排序。内部的for循环相当于对每个子序列进行直接插入排序，从当前的记录i(保存在r[0]中)开始，依次扫描当前子序列之前的元素(每个元素的间隔为d，因此每次循环j都减少d)以确保插入何时的位置。

本文所涉及的排序算法源码可以在这里下载。

与页框分配函数的整个实现过程相比，页框释放函数的实现要简单的多。常用的页框分配函数接口有 __free_pages()和__free_page()，很明显后者是前者的特殊情况。

#define __free_page(page) __free_pages((page), 0)

void __free_pages(struct page *page, unsigned int order)
{
        if (put_page_testzero(page)) {
                if (order == 0)
                        free_hot_cold_page(page, 0);
                else
                        __free_pages_ok(page, order);
        }
}

释放页框函数在一开始也兵分两路：如果分配阶为0，那么直接通过per-CPU机制来释放单一页框；否则通过__free_pages_ok()释放所申请的页框块。

1.__free_pages_ok()

该函数内部经过一些检查，这些检查是确保稍候对页框的释放是安全的，最终会调用free_one_page()，而它内部又封装了__free_one_page()。内核中函数之间的这种多次封装是很常见的，上层函数通过这种封装可以屏蔽某些参数，而底层的被封装的函数也可以被多种情况所引用。

static void __free_pages_ok(struct page *page, unsigned int order)
{
        …………
        free_one_page(page_zone(page), page, order, get_pageblock_migratetype(page));
        …………
}

static void free_one_page(struct zone *zone, struct page *page, int order,int migratetype)
{
        spin_lock(&zone->lock);
        zone->all_unreclaimable = 0;
        zone->pages_scanned = 0;

        __mod_zone_page_state(zone, NR_FREE_PAGES, 1 << order);
        __free_one_page(page, zone, order, migratetype);
        spin_unlock(&zone->lock);
}

在调用核心函数__free_one_page()之前，还需更新当前内存管理区的空闲页面数，其实就是将(1<vm_stat[NR_FREE_PAGES]上，其中vm_stat是一个对内存区进行信息统计的数组。

2.__free_one_page()

该函数按照伙伴算法的回收原理实现，从所请求的分配阶order开始，为当前页框块尽可能的寻找伙伴，进而合并成更大的页框块。在进入循环之前，先得到释放页框块的索引page_idx。

static inline void __free_one_page(struct page *page,
                struct zone *zone, unsigned int order,
                int migratetype)
{
        unsigned long page_idx;

        if (unlikely(PageCompound(page)))
                if (unlikely(destroy_compound_page(page, order)))
                        return;

        VM_BUG_ON(migratetype == -1);

        page_idx = page_to_pfn(page) & ((1 << MAX_ORDER) - 1);

        VM_BUG_ON(page_idx & ((1 << order) - 1));
        VM_BUG_ON(bad_range(zone, page));

        while (order < MAX_ORDER-1) {
                unsigned long combined_idx;
                struct page *buddy;

                buddy = __page_find_buddy(page, page_idx, order);
                if (!page_is_buddy(page, buddy, order))
                        break;

                list_del(&buddy->lru);
                zone->free_area[order].nr_free--;
                rmv_page_order(buddy);
                combined_idx = __find_combined_index(page_idx, order);
                page = page + (combined_idx - page_idx);
                page_idx = combined_idx;
                order++;
        }
        set_page_order(page, order);
        list_add(&page->lru,
                &zone->free_area[order].free_list[migratetype]);
        zone->free_area[order].nr_free++;
}

在每次的遍历过程中，通过__page_find_buddy()为当前页框块找一个伙伴buddy，这个伙伴可能在当前页框块之前，也可能在其之后。通过page_is_buddy()判断刚才找到的buddy是否能和欲释放的页框块进行合并。如果可以合并，则将这个buddy从它所处的页框块链表中删除，并更新nr_free的值，然后再通过rmv_page_order()更新buddy页框块首页框的相关标志。

接下来，通过__find_combined_index()寻找合并后页框块的索引combined_idx。由于page永远都指向要释放页框块的首页框描述符，因此根据combined_idx更新page和page_idx。同时，由于成功进行了伙伴合并，因此最后再将分配阶order加一。一旦没有可合并的伙伴（通过page_is_buddy()而break），整个合并过程也将结束，即退出循环。

接下来就要将页框块进行释放，其实就是将合并后的页框块（也许并没有合并，还是合并之前的那个页框块）插入到具体的分配阶链表中，并设置首页框的相关标志，将nr_free加一。要释放的页框块由page指定，order则指明了应该将这个页框块插入到哪一个页框块链表中，而migratetype则更具体的指明了要将该页框块插入哪一个迁移列表中。这些操作和之前伙伴算法中页框分配的过程是相反的。

3.__page_find_buddy()

前文已经说过，这个函数用于寻找当前要释放页框块的伙伴。具体的办法是先通过异或求出伙伴的索引，再根据此索引求出伙伴页框块的首页框描述符。

static inline struct page *
__page_find_buddy(struct page *page, unsigned long page_idx, unsigned int order)
{
        unsigned long buddy_idx = page_idx ^ (1 << order);

        return page + (buddy_idx - page_idx);
}

由于buddy_idx-page_idx的值可能为正也可能为负，因此伙伴页框块可能在当前页框块之前，也可能在其之后。

4.__find_combined_index()

该函数可以获得合并后页框块的索引。如果伙伴页框在当前页框块之后，那么这个函数返回的索引还是原来的值page_idx。如果伙伴页框在当前页框之前，那么合并后页框的索引其实是伙伴页框的索引。

static inline unsigned long
__find_combined_index(unsigned long page_idx, unsigned int order)
{
        return (page_idx & ~(1 << order));
}

至此基于伙伴算法的页框分配过程完毕。