目录
冒泡排序：
原理：基于交换的排序，每一轮将序列中的最大值（最小值）放到数组的尾部。使用循环重复操作，（每轮排序都会少一个最大值或最小值），当最后只剩下一个数据的时候整个序列就已经排好序了。
代码思路：从第一个数开始，每一次在数组中选两个数继续比较，如果前面的数大于后面的数，就将两者交换位置，第一次是1，2两个位置比较，第二次就是2,3两个位置比较，以此类推
//采用两层循环实现的方法//arr是待排序数组的首地址，n是数组元素个数voidbubblesort1(int*arr, intn) { if (n<2) return ;//数组个数小于2不需要排序inti;//排序次数intj;//每次排序元素位置inttmp;//交换位置时的临时变量for (i=n-1; i>0; i--)//一共进行n-1次 { for (j=0; j<i; j++)//每次比较0和i之前的元素，i之后已经排好 { if (arr[j] >arr[j+1])//如果前面大于后面，则交换位置 { tmp=arr[j+1]; arr[j+1] =arr[j]; arr[j] =tmp; } } } }
直接使用两层循环去实现，外层循环主要作用改变次数，保存最小值（最大值），内存循环的主要作用是找到发生冲突的元素，如果发生冲突就交换两个数据。当两层循环的结束的时候整个序列就自然排好序了
此外，还有一种方法：
//采用递归的方法voidbubblesort2(int*arr, intn) { if (n<2) return;//数组个数小于2不需要排序intj;//每次排序元素位置inttmp;//交换位置时的临时变量for (j=0; j<n-1; j++)//每次比较0和n-1之前的元素，n-1之后已经排好 { if (arr[j] >arr[j+1])//如果前面大于后面，则交换位置 { tmp=arr[j+1]; arr[j+1] =arr[j]; arr[j] =tmp; } } bubblesort2(arr, --n); }
递归方法和两层循环方法相似，只是将第一次的循环以递归的形式展现
intmain() { intarr[15] = { 44,3,38,5,47,15,36,26,24,2,46,4,19,50,48 }; //bubblesort1(arr, 15);bubblesort2(arr, 15); for (inti=0; i<15; i++) { printf("%d ", arr[i]); } printf("\n"); return0; }
运行结果：
选择排序：
原理：基本思想和冒泡排序是一样的，选择排序相对于冒泡排序的优点就是减少交换次数。算法思想都是在序列中找到最大值（最小值），然后存放好下次进入循环就访问不到这个最大值（最小值）。当两层循环都结束的时候序列就自然排好了。
代码思路：从第一个元素开始，往后寻找，在n个数中找到最小的值，将其与第一个元素交换位置，然后从第二个元素开始继续往后寻找，在n-1个元素中找到最小的元素，与第二个元素交换位置，以此类推
//采用两层循环实现的方法//arr是待排序数组的首地址，n是数组元素个数voidselectsort1(int*arr, intn) { if (n<2) return;//数组个数小于2不需要排序inti;//排序次数intj;//每次排序元素位置inttmp;//每次循环时最小的元素位置for (i=0; i<n-1; i++)//一共进行n-1次比较 { tmp=i; for (j=i+1; j<n; j++)//每次只需要比较i+1和n-1之间的元素，i之前的是已经排序号的 { if (arr[j] <arr[tmp])//找到值更小的元素，记下位置tmp=j; } if (tmp!=i)//如果此次循环的最小元素表示起始位置的元素，就交换他们的位置 { intk=arr[tmp]; arr[tmp] =arr[i]; arr[i] =k; } } }
同样的，与冒泡排序类似，选择排序也可以转换为递归形式：
//采用递归的方法voidselectsort2(int*arr, intn) { intj;//每次排序元素位置inttmp=0;//每次循环时最小的元素位置for (j=1; j<n; j++)//每次只需要比较i+1和n-1之间的元素，i之前的是已经排序号的 { if (arr[j] <arr[tmp])//找到值更小的元素，记下位置tmp=j; } if (tmp!=0)//如果此次循环的最小元素表示起始位置的元素，就交换他们的位置 { intk=arr[tmp]; arr[tmp] =arr[j]; arr[j] =k; } selectsort2(arr+1, --n); }
插入排序：
原理：基本思想还是冒泡排序，不过插入排序是两边相靠的冒泡，所以在序列部分有序的情况下，插入排序的效率要比冒泡排序效率高。从序列的尾部开始往前比较，如果当前的数据小于（大于）前一个的数据就进行交换，否则进入下一次循环，直到外层循环遍历完整个序列就自然排好序了。
代码思路：从第二个元素开始，将第二个元素与前面第一个元素比较，如果比第一个元素大则位置不变，如果比他小则将第一个位置元素后移，将第二个位置的元素插入第一个位置，以此类推，让第三个元素与前面两个元素比较，如果第三个元素大于第二个位置的元素，则不变，如果小于第二个位置的元素，就将第二个位置的元素后移到第三个位置（此时第二个位置空缺），然后原来第三个元素再与第一个位置的元素比较，如果大于则顺理成章插入到第二个位置中，如果小于则第一个位置的元素后移，将原第三个位置的元素插入第一个位置
voidinsertsort(int*arr,intn) { if (n<2) return;//数组个数小于2不需要排序inti;//待排序的元素intj;//每次插入时需要后移的元素inttmp;//当前需要排序的元素的值for (i=1; i<n; i++) { tmp=arr[i];//待排序的元素//从已排序的最右边开始，把大于当前排序的元素后移for (j=i-1; j>=0; j--) { if (arr[j] <=tmp) break; arr[j+1] =arr[j]; } //插入当前排序元素arr[j+1] =tmp; } } intmain() { intarr[15] = { 44,3,38,5,47,15,36,26,24,2,46,4,19,50,48 }; insertsort(arr, 15); for (inti=0; i<15; i++) { printf("%d ", arr[i]); } printf("\n"); return0; }
运行结果：
希尔排序：
原理：希尔排序是建立在插入排序的基础上进行优化的排序算法，所以希尔排序又叫做优化版的插入排序。
希尔排序的基本思想是把待排序的数列分为多组，然后再对每个组进行插入排序，先让数列整体大致有序，然后多次调整分组方式，使数列更加有序，最后再使用一次插入排序，使整个数列全部有序
代码思路：先将整个数组一分为二，再将每个组相同位置的元素比较大小，如果第二个组第一个元素小于第一个组第一个元素，就将两者交换位置，然后比较两个组第二个位置的元素大小，将两个组都比较完以后，再次分组，这一次将两个组各一分为二，各自比较，分到最后就变成了每个元素一一比较
//对希尔排序中的单个组进行排序voidgroupsort(int*arr,intn,intpos,intstep) { inti;//待排序的元素intj;//每次插入时需要后移的元素inttmp;//当前需要排序的元素的值for (i=pos+step; i<n; i=i+step) { tmp=arr[i];//待排序元素for (j=i-step; j>=0; j=j-step) { if (arr[j] <=tmp) break; arr[j+step] =arr[j]; } arr[j+step] =tmp; } } //希尔排序voidshellsort(int*arr,intn) { intstep;//每组个数，每次减为原来的一半取整数，最后一次必定为1for (step=n/2; step>0; step=step/2) { for (inti=0; i<step; i++) { groupsort(arr, n, i, step); } } }
