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] = pivotreturn 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);}}