一.直接插入排序
/*** @description: 直接插入排序算法* @param - a : 要进行排序的数组的指针* @return : 无
*/
void Seqsort(int *a)
{/* i 用于表示无序部分的第一个元素的下标 , j 用于表示有序部分的最后一个元素的下标 , temp 用于保存中间值 */int i,j,temp;/* 1.初始情况 , 将数组的 a[0] 与后面的元素分开,即 i 从 1 开始 */for(i = 1;i < N;i++){temp = a[i];/* 2. j 指向已排好序部分的最后一个元素的下标 */for(j = i-1;j >= 0;j--){ /* 若 a[i] < a[j] 则 a[j] 向后移动 */if(temp < a[j])a[j+1] = a[j];/* 若 a[i] >= a[j] 则跳出循环 */elsebreak;}/* 若 a[i] >= a[j] 则 a[j+1] = a[i] */a[j+1] = temp;Show(a);}}
二.shell排序算法 - 对直接插入排序的改进
1.shell排序的步骤
①.对序列进行分组,增量为 d
②.对每一组 分别 / 交替 直接插入排序
③.逐渐减小增量 d
2.图形讲解
3.代码
/*** @description: shell排序* @param -a : 要进行排序的数组的指针* @return : 无
*/
void Shell_sort(int *a)
{/* i 用于表示无序部分的第一个元素的下标 , j 用于表示有序部分的最后一个元素的下标 , temp 用于保存中间值 */int i,j,temp;int d;/* 初始化 d = N / 2 , 然后 d 持续减小 */for(d = N/2;d > 0;d /= 2){/* 1.将数组的同一组元素进行直接插入排序 */for(i = d;i < N;i++){temp = a[i];/* 2. j 指向已排好序部分的最后一个元素的下标 ,同一组内的元素每两个相邻的元素之间的距离为 d */for(j = i-d;j >= 0;j -= d){ /* 若 a[i] < a[j] 则 a[j] 向后移动 , 移动的步长为 d */if(temp < a[j])a[j+d] = a[j];/* 若 a[i] >= a[j] 则跳出循环 */elsebreak;}/* 若 a[i] >= a[j] 则 a[j+d] = a[i] */a[j+d] = temp;}Show(a);}}
三.快速排序算法
1.快速排序图形讲解
2.代码
利用 递归
①.经过一趟快速排序后,确认基准位置
②.该基准将整个数组分为左右两部分
③.分别对左右两部分进行快速排序
/*** @description: 一趟的快速排序* @param - a : 要排序的数组的指针* @param - i : 下界元素的下标* @param - j : 上界元素的下标* @return : 基准元素的下标
*/
int Quickpass(int *a,int i,int j)
{int temp;/* 当上界小于下界时进行一趟的快速排序 *//* 1.保存基准的值 */temp = a[i];while(i < j){/* 2.比较 temp 与 a[j] 的大小,若 temp <= a[j] , 则 j-- ,若 temp > a[j] 则将 a[j] 的值赋给 a[i] */while(i < j && temp <= a[j]){j--;}if(i < j) //若正常结束循环{a[i] = a[j]; //temp > a[j] 则将 a[j] 的值赋给 a[i]}/* 3.比较 temp 与 a[i] 的大小 , 若 temp >= a[i] , 则 i++ , 若 temp < a[i] , 则将 a[i] 的值赋给 a[j] */while(i < j && temp >= a[i]){i++;}if(i < j) //若正常结束循环{a[j] = a[i]; //temp < a[i] , 则将 a[i] 的值赋给 a[j]}}/* 4.一趟快速排序结束后 , 将一开始保存的基准的值 temp 重新加入到序列中 */a[i] = temp;/* 5.返回基准元素的下标 */return i;
}/*** @description: 快速排序* @param - a : 要排序的数组的指针* @param - low : 下界元素的下标* @param - high : 上界元素的下标* @return : 无
*/
void Quick_sort(int *a,int low,int high)
{int mid; // mid 用于存储基准的位置if(low < high){mid = Quickpass(a,low,high); //一趟的快速排序Show(a);Quick_sort(a,low,mid-1); //基准左边的序列进行快速排序Quick_sort(a,mid+1,high); //基准右边的序列进行快速排序}
}