[数据结构与算法]排序内容总结

大根堆

完全二叉树中如果每棵子树的最大值都在顶部就是大根堆
时间复杂度O(log N)

//某个数处在index位置，比父大，往上继续移动
int heapInsert(int nums[], int index)
{
	while(nums[index] > nums[(index - 1) / 2])
	{
		swap(nums, index, (index - 1) / 2);
		index = (index - 1) / 2;
	}
}
int swap(int nums[], int i, int j)
{
	nums[i] = nums[i] ^ nums[j];
	nums[j] = nums[i] ^ nums[j];
	nums[i] = nums[i] ^ nums[j];
}

去除堆中最大值，其余仍为大根堆结构

时间复杂度O(log N)

//某个数在index位置，能否往下移动
int heapify(int nums[], int index, int heapSize)
{
	int left = index * 2 + 1; //左孩子下标
	while(left < heapSize) //下方还有孩子的时候
	{
		//左右两个孩子，谁的值大，把下标给larget
		if(left + 1 < heapSize && nums[left + 1] > nums[left])
		{
			int largest = left + 1;
		}else largest = left;
		//较大的孩子和父之间，谁的值大，把下标给largest
		if(nums[largest] > nums[index])
		{
			largest = largest;
		}else largest = index;
		if(largest = index){break;} //largest 等于父节点
		swap(nums, largest, index);
		index = largest; //新的父节点
		left = index * 2 + 1;
	}
}
int swap(int nums[], int i, int j)
{
	nums[i] = nums[i] ^ nums[j];
	nums[j] = nums[i] ^ nums[j];
	nums[i] = nums[i] ^ nums[j];
}

1、堆排序

时间复杂度O(N * log N)，额外空间复杂度O(1)

#include <stdio.h> 

int main()
{
	int i;
	int nums[] = {3,4,3,6,2};
	int numsSize = sizeof(nums) / sizeof(int); 
	heapSort(nums, numsSize); //堆排序法
	for(i = 0; i < numsSize; i++)
	{
		printf("%d", nums[i]);
	}
}

int heapSort(int nums[], int numsSize)
{
	int i;
	int heapSize = numsSize;
	if(nums == NULL || numsSize < 2) {return;}
//	for(i = 0; i < numsSize; i++) //O(N)
//	{
//		heapInsert(nums, i); //O(log N)
//	}
	//稍快写法
	for(i = numsSize - 1; i >= 0; i--) //整个数组变成大根堆
	{
		heapify(nums, i, heapSize); //O(log N)
	}
	
	//0位置的数和堆上最后一个位置的数交换
	swap(nums, 0, --heapSize); //交换完成后堆大小--
	while(heapSize > 0) //O(N)
	{
		heapify(nums, 0, heapSize); //O(log N)
		swap(nums, 0, --heapSize); //O(1)
	}
}

//某个数处在index位置，比父大，往上继续移动
int heapInsert(int nums[], int index)
{
	while(nums[index] > nums[(index - 1) / 2])
	{
		swap(nums, index, (index - 1) / 2);
		index = (index - 1) / 2;
	}
}

//某个数在index位置，能否往下移动
int heapify(int nums[], int index, int heapSize)
{
	int largest;
	int left = index * 2 + 1; //左孩子下标
	while(left < heapSize) //下方还有孩子的时候
	{
		//左右两个孩子，谁的值大，把下标给larget
		if(left + 1 < heapSize && nums[left + 1] > nums[left])
		{
			largest = left + 1;
		}else largest = left;
		//较大的孩子和父之间，谁的值大，把下标给largest
		if(nums[largest] > nums[index])
		{
			largest = largest;
		}else largest = index;
		if(largest = index){break;} //largest 等于父节点
		swap(nums, largest, index);
		index = largest; //新的父节点
		left = index * 2 + 1;
	}
}

int swap(int nums[], int i, int j)
{
	int temp = nums[i];
	nums[i] = nums[j];
	nums[j] = temp;
}