选择排序算法【直接选择排序，堆排序】C代码

选择排序算法【直接选择排序，堆排序】C代码

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

void arrPrintf(int* data, int length)
{
	for (size_t i = 0; i < length; i++)
	{
		if (i == length - 1)
			printf("%2d\n", data[i]);
		else
			printf("%2d, ", data[i]);
	}

}

//直接选择排序
void selectSort(int* data, int length)
{
	int min = 0,index = 0;
	for (size_t i = 0; i < length-1; i++)
	{
		min = data[i];//最小元素
		index = i;//对应索引
		
		//找到最小元素及其索引位置
		for (int j = i+1; j < length; j++)
		{
			if (data[j] < min)
			{
				min = data[j];
				index = j;
			}
		}
		//交换位置
		int temp = data[i];
		data[i] = min;
		data[index] = temp;
		
		printf("第 %2d 次排序 ： ", i+1);
		arrPrintf(data, length);
	}
	
}

//交换
void swap(int* data, int i, int j)
{
	int temp = data[i];
	data[i] = data[j];
	data[j] = temp;
}


//构建大顶堆
void buildMaxHeap(int* data, int length)
{
	//从 n/2 的下标开始，向前做调整
	/*
	* 长度为5
				9 6 7 4 10
	实际下标	    0 1 2 3 4
	*/
	int n = length / 2 - 1;//实际下标从0开始，故这里需要减1
	for (int i = n; i >= 0; i--)
	{
		int left = 2 * i + 1;//左子树下标
		int right = 2 * i + 2;//右子树下标
		if (data[left] > data[i])
		{
			swap(data, i, left);
		}
		if (data[right] > data[i] && right <= length -1)
		{
			swap(data, i, right);
		}
	}
}

//堆排序
void HeapSort(int* data, int length)
{
	//先构建大顶堆
	buildMaxHeap(data, length);

	//进行循环移动
	int index = 0;
	for (int i = length-1; i > 0; i--)
	{
		index++;
		//交换
		swap(data, 0, i);
		//重新构建大顶堆
		buildMaxHeap(data, i);

		printf("第 %2d 次排序 ： ", index);
		arrPrintf(data, length);
	}
	
}

int main()
{
	//选择排序
	printf("选择排序算法\n");

	/*
	稳定：若有2个相等的键值元素，在排序前后它们的相对位置保持不变，比如【2，3，5_a,5_b】（这里5_a，5_b为值相同的元素）
		  在排序后5_a依然在5_b前面，则相对位置保持；否则称为不稳定
	归位：比较过就可以确定元素的位置
	
	选择排序：不稳定，归位

	思路：
	1.从第一个元素开始，进行一趟对比后，找到最小的元素，并将最小元素放在第一个位置
	2.从第二个元素开始，进行一趟对比后，找到最小的元素，并将最小元素放在第二个位置
	3.依次类推，直到n-1趟后，排序完毕

	*/
	int data[] = {2,5,29,15,39,98,41,3,55,55,20,78,18,88};
	arrPrintf(data, sizeof(data) / sizeof(data[0]));
	printf("排序前后--数据长度：%d\n", sizeof(data)/sizeof(data[0]));
	selectSort(data, sizeof(data) / sizeof(data[0]));
	arrPrintf(data, sizeof(data) / sizeof(data[0]));
	/*
	选择排序算法
					 2,  5, 29, 15, 39, 98, 41,  3, 55, 55, 20, 78, 18, 88
	排序前后--14
	第  1 次排序 ：  2,  5, 29, 15, 39, 98, 41,  3, 55, 55, 20, 78, 18, 88
	第  2 次排序 ：  2,  3, 29, 15, 39, 98, 41,  5, 55, 55, 20, 78, 18, 88
	第  3 次排序 ：  2,  3,  5, 15, 39, 98, 41, 29, 55, 55, 20, 78, 18, 88
	第  4 次排序 ：  2,  3,  5, 15, 39, 98, 41, 29, 55, 55, 20, 78, 18, 88
	第  5 次排序 ：  2,  3,  5, 15, 18, 98, 41, 29, 55, 55, 20, 78, 39, 88
	第  6 次排序 ：  2,  3,  5, 15, 18, 20, 41, 29, 55, 55, 98, 78, 39, 88
	第  7 次排序 ：  2,  3,  5, 15, 18, 20, 29, 41, 55, 55, 98, 78, 39, 88
	第  8 次排序 ：  2,  3,  5, 15, 18, 20, 29, 39, 55, 55, 98, 78, 41, 88
	第  9 次排序 ：  2,  3,  5, 15, 18, 20, 29, 39, 41, 55, 98, 78, 55, 88
	第 10 次排序 ：  2,  3,  5, 15, 18, 20, 29, 39, 41, 55, 98, 78, 55, 88
	第 11 次排序 ：  2,  3,  5, 15, 18, 20, 29, 39, 41, 55, 55, 78, 98, 88
	第 12 次排序 ：  2,  3,  5, 15, 18, 20, 29, 39, 41, 55, 55, 78, 98, 88
	第 13 次排序 ：  2,  3,  5, 15, 18, 20, 29, 39, 41, 55, 55, 78, 88, 98
	*/

	/*
	堆排序：堆是一种特殊的树，需要满足以下两点
	1.堆是一个完全二叉树
	2.堆的每一个节点的值都必须大于等于（或小于等于）其子树中的每个节点的值
	
	对于一个完全二叉树来说，使用数组存储是非常节省空间的。
	我们可以单纯的通过数组下标找到一个节点的左右子节点和父节点

	1.先构建堆，我们以大顶堆为例
	由于叶子节点向下调整只能自己跟自己比较，所以我们直接从最后一个非叶子节点开始，
	依次向下调整
			⑨                          		⑨								⑩                    
		   /  \							   /  \							   /  \
		  ⑥    ⑦    -->      			  ⑩    ⑦    -->      			  ⑨    ⑦          
		 / \   						     / \   							 / \   
		④   ⑩						  	④   ⑥						    ④   ⑥
	| 9 | 6 | 7 | 4 | 10 |			| 9 | 10 | 7 | 4 | 6 |		      | 10 | 9 | 7 | 4 | 6 |
	  0   1   2   3   4    			  0   1    2   3   4   		        0    1   2   3   4   
	如图所示n为5，我们从下标为n/2-1开始一直到1的数据进行向前调整，下标n/2到n是叶子节点，不用调整

	2.排序，大顶堆构建完毕后，数组下标为1的元素就是最大元素，也及堆顶；
	将它与最后一个元素进行交换，然后继续构建大顶堆；
	将堆顶元素与倒数第二个元素交换，依此类推，直到堆中剩下下标为1的元素。

	堆排序：不稳定，归位

	*/
	printf("堆排序算法\n");
	int data1[] = { 2,5,29,15,39,98,41,3,55,55,20,78,18,88,1,99,50};
	int length1 = sizeof(data1) / sizeof(data1[0]);
	printf("第 %2d 次排序 ： ", 0);
	arrPrintf(data1, length1);
	HeapSort(data1, length1);
	arrPrintf(data1, length1);
	/*
	堆排序算法
	第  0 次排序 ：  2,  5, 29, 15, 39, 98, 41,  3, 55, 55, 20, 78, 18, 88,  1, 99, 50
	第  1 次排序 ： 98, 50, 55,  2, 55, 78, 88,  5, 15, 39, 20, 29, 18, 41,  1,  3, 99
	第  2 次排序 ： 88,  3, 55, 15, 50, 55, 78,  2,  5, 39, 20, 29, 18, 41,  1, 98, 99
	第  3 次排序 ： 78,  1, 50,  3, 15, 55, 55,  2,  5, 39, 20, 29, 18, 41, 88, 98, 99
	第  4 次排序 ： 55, 39, 41,  1,  5, 50, 55,  2,  3, 15, 20, 29, 18, 78, 88, 98, 99
	第  5 次排序 ： 55, 18, 39,  3, 20, 41, 50,  1,  2,  5, 15, 29, 55, 78, 88, 98, 99
	第  6 次排序 ： 50, 20, 29,  3, 18, 39, 41,  1,  2,  5, 15, 55, 55, 78, 88, 98, 99
	第  7 次排序 ： 41, 15, 20,  3, 18, 29, 39,  1,  2,  5, 50, 55, 55, 78, 88, 98, 99
	第  8 次排序 ： 39,  5, 18,  3, 15, 20, 29,  1,  2, 41, 50, 55, 55, 78, 88, 98, 99
	第  9 次排序 ： 29,  2, 15,  3,  5, 18, 20,  1, 39, 41, 50, 55, 55, 78, 88, 98, 99
	第 10 次排序 ： 20,  1,  5,  2,  3, 15, 18, 29, 39, 41, 50, 55, 55, 78, 88, 98, 99
	第 11 次排序 ： 18,  3, 15,  1,  2,  5, 20, 29, 39, 41, 50, 55, 55, 78, 88, 98, 99
	第 12 次排序 ： 15,  3,  5,  1,  2, 18, 20, 29, 39, 41, 50, 55, 55, 78, 88, 98, 99
	第 13 次排序 ：  5,  2,  3,  1, 15, 18, 20, 29, 39, 41, 50, 55, 55, 78, 88, 98, 99
	第 14 次排序 ：  3,  1,  2,  5, 15, 18, 20, 29, 39, 41, 50, 55, 55, 78, 88, 98, 99
	第 15 次排序 ：  2,  1,  3,  5, 15, 18, 20, 29, 39, 41, 50, 55, 55, 78, 88, 98, 99
	第 16 次排序 ：  1,  2,  3,  5, 15, 18, 20, 29, 39, 41, 50, 55, 55, 78, 88, 98, 99
	*/
	

	return 0;
}