swap简单实现
bool swap(int *pointer1, int *pointer2) { if (pointer1== NULL || pointer2== NULL){ return false; } if (pointer1!= pointer2) { int temp = *pointer1; *pointer1= *pointer2; *pointer2= temp; } return true; }
冒泡排序：常规冒泡、优化后的冒泡
算法思想:
从左到右扫描数据,找出最大的元素,将其放到数组右边;
过程:
循环比较相邻的两个数,如果左边的数比右边的大,则交换两个数;
//1 常规的冒泡排序 void bobble_sort(int *data, int length) { for (int i = 0; i < length - 1 ; i++) { //趟数 for (int j = 0; j < length - i -1 ; j++) { //比较次数 if (*(data + j) > *(data + j + 1)) { swap(data + j, data + j + 1); } } } } //2 优化后的冒泡排序 void next_bobble_sort(int *data, int len) { int i, j; int temp; int flag = 0; for (i = 0; i < len&&flag == 0; ++i) { flag = 1; for (j = 1; j < len - i; j++) { if (data[j] < data[j - 1]) { temp = data[j]; data[j] = data[j - 1]; data[j - 1] = temp; flag = 0; } } } }
平均时间复杂度：O(n^2) 最好时间复杂度：O(n) 最坏时间复杂度：O（n^2） 空间复杂度：O(1) 稳定性：稳定 排序方式：内排
选择排序：
思想:
从当前尚未排序的序列中选择一个最小的元素, 将之放到已排序的序列的队列的末尾;
要点:
1.注意min所代表的含义;
2.同时注意是从未排序的序列中进行查找最小元素!
void select_sort(int *data, int length) { int min; for (int i = 0; i < length -1; i++) { min = i; for (int j = i + 1; j < length; j++) { if (*(data + j) < *(data + min)) { swap(data + j, data + min); } } } }
平均时间复杂度：O(n^2) 最好时间复杂度：O(n^2) 最坏时间复杂度：O（n^2） 空间复杂度：O(1) 稳定性：不稳定 排序方式：内排
插入排序：直接插入排序，二分插入排序，希尔排序(另博客讨论)
算法思想:
不断的从尚未排序的序列中选择一个元素插入到已经排好序的序列中(当然,会有一个选择插入位置的过程:选择一个位置, 该位置前的元素都比该元素小, 该位置后的元素都比该元素大),类似于现实生活中的斗地主的摸排过程.
//1 直接插入排序 void direct_insert_sort(int *data, int length) { int j; //循环变量 int temp; //存储待排序元素 for (int i = 1; i < length; i++) { j = i; temp = data[i]; //待排序元素赋值给临时变量 while (j > 0 && temp < data[j - 1]) { //当未达到数组的第一个元素或者待插入元素小于当前元素 data[j] = data[j - 1]; //就将该元素后移 j--; //下标减一，继续比较 } data[j] = temp; //插入位置已经找到，立即插入 } } //2 二分插入排序 void bin_insert_sort(int *data, int length) { for (int i = 1; i<length; i++) { int left = 0; int right = i - 1; int temp = data[i]; while (left <= right) { int mid = (left + right) / 2; //二分区域 if (data[mid]>temp) { right = mid - 1; //向左缩小区域 } else { left = mid + 1; //向右缩小区域 } } for (int j = i - 1; j>left; j--) //data[left,i-1]的元素整体后移 { data[j + 1] = data[i]; } data[left] = temp; } }
平均时间复杂度：O(n^2) 最好时间复杂度：O(n) 最坏时间复杂度：O（n^2） 空间复杂度：O(1) 稳定性：稳定 排序方式：内排
