C语言数据结构编程练习-排序算法

1、冒泡排序

 思路：比较相邻的两个数，左边大于右边交换一趟排下来最大的在右边时间复杂度：O(n2)

//冒泡排序  从小到大的顺序排列
//思路：比较相邻的两个数，左边大于右边交换一趟排下来最大的在右边
void bubbleSort(int arr[],int length)
{
	for (int i = 0; i < length-1; i++)//比较的趟数：length-1趟
	{
		for (int j = 0; j < length - 1 - i; j++)//每趟比较的次数:length-1-i
		{
			if (arr[j] > arr[j + 1])
			{
				int temp = arr[j];
				arr[j] = arr[j + 1];
				arr[j + 1] = temp;
			}
		}
	}

}

2、选择排序

思路：每次从待排序列中选出一个最小值，然后放在序列的起始位置，直到全部待排数据排完即可。
实际上，我们可以一趟选出两个值，一个最大值一个最小值，然后将其放在序列开头和末尾，这样可以使选择排序的效率快一倍。 

//选择排序
// 时间复杂度：O(n2)
//思路：每次从待排序列中选出一个最小值，
// 然后放在序列的起始位置，直到全部待排数据排完即可。
void selectionSort1(int arr[], int length)
{
	int min = 0;
	for (int i = 0; i < length; i++)
	{
		for (int j = i; j < length; j++)
		{
			if (arr[min] > arr[j])
			{
				int temp = arr[min];
				arr[min] = arr[j];
				arr[j] = temp;
			}
		}
		min++;
	}

}

//优化升级：实际上，我们可以一趟选出两个值，一个最大值一个最小值，
//然后将其放在序列开头和末尾，这样可以使选择排序的效率快一倍。
void selectionSort2(int arr[], int length)
{
	int min = 0;
	int max = length - 1;
	for (int i = 0; i < length; i++)
	{
		for (int j = i; j < length-i; j++)
		{
			if (arr[min] > arr[j])
			{
				int temp = arr[min];
				arr[min] = arr[j];
				arr[j] = temp;
			}
			if (arr[max] < arr[j])
			{
				int temp = arr[max];
				arr[max] = arr[j];
				arr[j] = temp;
			}
		}
		min++;
		max--;
	}

}

3、插值排序

思路：
  在待排序的元素中，假设前n-1个元素已有序，现将第n个元素插入到前面已经排好的序列中，使得前n个元素有序。按照此法对所有元素进行插入，直到整个序列有序。
  但我们并不能确定待排元素中究竟哪一部分是有序的，所以我们一开始只能认为第一个元素是有序的，依次将其后面的元素插入到这个有序序列中来，直到整个序列有序为止。

 //插值排序       从小到大的顺序排列
void insertSort1(int arr[], int length)
{
	//假设第1个元素就是有序序列，直接从第2个元素开始插入
	for (int i = 1; i < length; i++)
	{
		int end = i;//有序序列的结束位置   也是待排的插入数据
		int temp = arr[i];//记录待排序数值
		while (end > 0)
		{
			if (arr[end - 1] > temp)
			{
				arr[end] = arr[end - 1];
				end--;
			}
			else
			{
				break;
			}
		}
		arr[end] = temp;
	}

}

//插值排序的另一种写法：     从小到大排序
void insertSort2(int arr[], int length)
{
	for (int i = 1; i < length; i++)
	{
		int end = i;//有序序列的结束位置   也是待排的插入数据
		int temp = arr[i];//记录待排序数值
		for (int j = i; j >= 0; j--) 
		{
			if (arr[j-1] > temp)//后移
			{
				arr[j] = arr[j - 1];//后移
				end--;
			}
			else
			{
				break;
			}
		}
		arr[end] = temp;
	}

}

4、快速排序

/*快速排序,说白了就是给基准数据找其正确索引位置的过程*/
int getIndex(int arr[], int low, int high)
{
	int pivot = arr[low];//pivot  支点

	while (low < high)
	{
		while (low < high && arr[high] >= pivot)
		{
			high--;
		}
		arr[low] = arr[high];

		while (low < high && arr[low] <= pivot)
		{
			low++;
		}
		arr[high] = arr[low];
	}
	arr[low] = pivot;//arr[high] = pivot
	return low;//return high
}

//快速排序，使用递归
void quickSort(int arr[], int low, int high)
{
	if (low < high)
	{
		int temp = getIndex(arr, low, high);

		quickSort(arr, low, temp - 1);
		quickSort(arr, temp + 1, high);
	}

}