简单插入排序
选当前数作为要插入的数据，从后往前看是否有比当前还小的， 如果有就进行交换 最后将当前数放入要插入的位置
void insert_sort(int* data , int length){ int i; for(int i = 1 ; i < length - 1; i++){ int index = data[i]; //哨兵 暂存数据 int j; for(j = i ; j > 0 && index < data[j-1] ; j--){ data[j] = data[j-1]; } if(j != i){ // 要插入的数据比前面小 否则没有进行交换直接进入下一次循环 data[j] = index; } } }
选择排序
每次拿当前数作为最小值 ， 往后遍历 ， 找到比最小值还小的数 ， 更新下标 ， 最后和当前数进行交换
void select_sort(int *data , int length){ int i; for(int i = 0 ; i < length - 1; i++){ int min = i; // 默认当前为最小 int j; for(j = i+1 ; j < length ; j++){ //遍历找到最小的下标 if(data[j] < data[min]) min = j; // 更新最小下标 } if(i != min){ // 如果找到比当前还小就交换 int temp = data[i]; data[i] = data[min]; data[min] = temp; } } }
希尔排序:
1. 分组
2. 遍历每个组
3. 组内进行插入排序
// 希尔排序 int shell_sort(int *data , int length){ int gap = 0; // 分组的跨度 int j , i; for(gap = length/2 ; gap >= 1 ; gap/=2){ //分组的次数 for(i = gap ; i < length ; i++){ //每次分组之后对组进行遍历 int temp = data[i]; for(j = i - gap ; j >= 0&&temp < data[j] ; j = j - gap){//组内循环 data[j+gap] = data[j]; } data[j+gap] = temp; } } return 0; }
快速排序
int sort(int *data , int left , int right){ if(left > right) return 0; int i = left; int j = right; int key = data[left]; // 哨兵 while(i < j){ while(i < j && key < data[j]) j--; //从又往左找比哨兵小的数 data[i] = data[j]; //交换 while(i < j && key > data[i]) i++; //从左找比哨兵大的数 data[j] = data[i]; // 交换 } // i == j data[i] = key; // 哨兵归位 // 递归 sort(data , left , i - 1); sort(data , i + 1 , right); } int quick_sort(int *data , int length){ sort(data , 0 , length - 1); }
