目录
冒泡排序（Bubble sorting）
选择排序（Select sort）
插入排序（Insert sort）
希尔排序（Shell Sort）
快速排序（Quick sort）
归并排序（Merge sort）
基数排序（Radix Sort）
冒泡排序（Bubble sorting）
冒泡排序算法的原理如下：
-
比较相邻的元素。如果第一个比第二个大，就交换他们两个。
-
对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
-
针对所有的元素重复以上的步骤，除了最后一个。
-
持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
冒泡排序算法时间复杂度：
#include#include #include #define N 200 int bubbleSort(int* arr, int num){ int temp; //定义临时遍历 int flag = 0; //定义标记 int i, j; for(i = 0; i < num - 1; i++){ for(j = 0; j < num - 1 - i; j++){ if(arr[j] > arr[j + 1]){ flag = 1; temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp; } } if(!flag){ //如果flag = 0，那么说明这一趟没有进行交换数据，则说明已经有序了 return 1; }else{ //如果交换了数据，那么要把flag重新置为0，方便下一轮标记 flag = 0; } } } int comp(const void*a,const void*b)//用来做比较的函数。 { return *(int*)a-*(int*)b; } int main(int argc, char *argv[]) { int num; //定义需要输入的数据的个数 int arr[N]; //定义一维数组 int i; time_t t; scanf("%d", &num); for(i = 0; i < num; i++){ scanf("%d", &arr[i]); } bubbleSort(arr, num); // qsort(arr, num, sizeof(int), comp); //测试qsort for(i = 0; i < num; i++){ printf("%d ", arr[i]); //打印已经排序好的数组 } return 0; }
选择排序（Select sort）
选择排序算法的原理如下：
第一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后再从剩余的未排序元素中寻找到最小（大）元素，然后放到已排序的序列的末尾。以此类推，直到全部待排序的数据元素的个数为零。
#include#include #define N 200 //选择排序 void selectSort(int* arr, int num){ int i, j; int min, minIndex; //min表示最小的元素，minIndex表示最小元素的下标 for(i = 0; i < num - 1; i++){ min = arr[i]; minIndex = i; for(j =i ; j < num; j++){ if(min > arr[j]){ //从小到大排序，若要从大到小排序则改为< min = arr[j]; minIndex = j; } } if(minIndex != i){ //数组后面存在元素比当前元素小的元素时才交换 arr[minIndex] = arr[i]; //更小元素的元素位置换为当前元素 arr[i] = min; //当前元素换位更小元素 } } } int main(int argc, char *argv[]) { int num; int arr[N]; int i; scanf("%d", &num); for(i = 0; i < num; i++){ scanf("%d", &arr[i]); } selectSort(arr, num); printf("选择排序后的结果为：n"); for(i = 0; i < num; i++){ printf("%d ",arr[i]); } return 0; }
插入排序（Insert sort）
插入排序算法的原理如下：
插入排序是指在待排序的元素中，假设前面n-1(其中n>=2)个数已经是排好顺序的，现将第n个数插到前面已经排好的序列中，然后找到合适自己的位置，使得插入第n个数的这个序列也是排好顺序的。按照此法对所有元素进行插入，直到整个序列排为有序 。
#include#include #define N 200 // 插入排序 void InsertSort(int* arr, int num){ int insertVal, insertIndex; int i; for(i = 1; i < num; i++){ insertVal = arr[i]; //将待插入的元素赋值给insertVal insertIndex = i - 1; //将待插入的元素下标赋值给insertIndex while(insertIndex >= 0 && insertVal < arr[insertIndex]) { //从后向前比较，若待插入元素比前面的元素小，则执行以下操作 arr[insertIndex + 1] = arr[insertIndex]; //比待插入元素大的元素后移 insertIndex--; //insertIndex - 1，待插入位置向前移一个位置，比较前一个元素 } if((insertIndex + 1) != i){ //判断待插入位置与原始位置是否一样，若不同则插入 arr[insertIndex + 1] = insertVal; } } } int main(int argc, char *argv[]) { int num; int arr[N]; int i; scanf("%d", &num); for(i = 0; i < num; i++){ scanf("%d", &arr[i]); } InsertSort(arr, num); printf("排序好的数组如下：n"); for(i = 0; i < num; i++){ printf("%d ", arr[i]); } return 0; }
希尔排序（Shell Sort）
希尔排序算法的原理如下：
希尔排序是按照不同步长对元素进行插入排序，当刚开始元素很无序的时候，步长最大，所以插入排序的元素个数很少，速度很快；当元素基本有序了，步长很小，插入排序对于有序的序列效率很高。
#include#include #define N 200 //交换法希尔排序 void shellSort(int *arr, int num){ int gap, i, j; int temp; //gap是步长，希尔排序每轮分组进行比较交换的数据间隔gap for(gap = num / 2; gap > 0; gap /= 2){ //当没有比较到最后一组时，继续执行 for(i = gap; i < num; i++){ //计算同一组的成员有谁 for(j = i - gap; j >= 0; j -= gap){ //如果前面的元素比后面的元素大，则交换两个数据 if(arr[j] > arr[j + gap]){ temp = arr[j]; arr[j] = arr[j + gap]; arr[j + gap] = temp; } } } } } //移位法希尔排序 void shellSort2(int *arr, int num){ int gap, temp, i, j; for(gap = num / 2; gap > 0; gap /= 2){ for(i = gap; i < num; i++){ j = i; temp = arr[i]; if(arr[j] < arr[j - gap]){ //temp比前面的元素小时，就将前面的元素后移 while(j - gap >= 0 && temp < arr[j - gap]){ arr[j] = arr[j - gap]; j -= gap; } //推出while循环，即找到合适的位置 arr[j] = temp; } } } } int main(int argc, char *argv[]) { int num, i; int arr[N]; scanf("%d", &num); for(i = 0; i < num; i++) scanf("%d", &arr[i]); //shellSort(arr, num); shellSort2(arr, num); //希尔排序排好后的结果 printf("希尔排序后的结果：n"); for(i = 0; i < num; i++){ printf("%d ",arr[i]); } return 0; }
快速排序（Quick sort）
1）设置两个变量i、j，排序开始的时候：i=0，j=N-1；
2）以第一个数组元素作为关键数据，赋值给key，即key=A[0]；
3）从j开始向前搜索，即由后开始向前搜索(j--)，找到第一个小于key的值A[j]，将A[j]和A[i]的值交换；
4）从i开始向后搜索，即由前开始向后搜索(i++)，找到第一个大于key的A[i]，将A[i]和A[j]的值交换；
5）重复第3、4步，直到i==j； (3,4步中，没找到符合条件的值，即3中A[j]不小于key,4中A[i]不大于key的时候改变j、i的值，使得j=j-1，i=i+1，直至找到为止。找到符合条件的值，进行交换的时候i， j指针位置不变。另外，i==j这一过程一定正好是i+或j-完成的时候，此时令循环结束）。
#include#include #define N 200 int getIndex(int* arr, int left, int right){ //基准数据 int temp = arr[left]; while(left < right){ //当右边数据大于等于基准数据时，向前移动right指针 while(left < right && arr[right] >= temp){ right--; } //如果找到比基准数据小的，将其赋值给arr[left] arr[left] = arr[right]; //当左边数据小于等于基准数据时，向后移动left指针 while(left < right && arr[left] <= temp){ left++; } //如果找到比基准数据大的，将其赋值给arr[right] arr[right] = arr[left]; } //while循环结束后，left == right //此时，找到基准数据在该数组中的正确位置 //比基准数据大的元素都在基准数据右边 ,比基准数据小的元素都在基准数据左边 //将正确位置赋值上基准数据 arr[left] = temp; //返回基准数据的正确位置，对左边、右边进行快速排序 return left; } void quickSort(int *arr, int left, int right){ int index; if(left < right){ //找基准数据的正确位置 index = getIndex(arr, left, right); //向左递归 quickSort(arr, left, index - 1); //向右递归 quickSort(arr, index + 1, right); } } int main(int argc, char *argv[]) { int num; int arr[N]; int i; scanf("%d", &num); for(i = 0; i < num; i++){ scanf("%d", &arr[i]); } quickSort(arr, 0, num - 1); printf("快速排序后数组为：n"); for(i = 0; i < num; i++){ printf("%d ", arr[i]); } return 0; }
归并排序（Merge sort）
第一步：申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
第二步：设定两个指针，最初位置分别为两个已经排序序列的起始位置
第三步：比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
重复步骤3直到某一指针超出序列尾
将另一序列剩下的所有元素直接复制到合并序列尾
#include#include //合并的方法 //arr：待排序数组，left：左边初始索引；mid：中间索引；right：右边索引；temp：临时数组 void merge(int *arr, int left, int mid, int right, int *temp){ //left和right是边界，i和j是索引 int i = left, j = mid + 1, t = 0, tempLeft = left; //t是temp数组的索引, tempLeft是后面复制temp是需要的 //(一) 将两边的数组中较小的元素放入temp while(i <= mid && j <= right){ if(arr[i] <= arr[j]){ temp[t] = arr[i]; //把较小的arr[i]赋值给temp t++; i++; }else{ temp[t] = arr[j]; t++; j++; } } //(二) 将左（或右）边没有放完的数据放到temp中 while(i <= mid){ temp[t] = arr[i]; t++; i++; } while(j <= right){ temp[t] = arr[j]; t++; j++; } //(三) 把temp复制到arr，因为每次不一定是从0复制到7，所以设置tempLeft和t for(t = 0, tempLeft = left; tempLeft <= right; t++, tempLeft++){ arr[tempLeft] = temp[t]; } } //分+合 void mergeSort(int *arr, int left, int right, int *temp){ int mid = (left + right) / 2; //left == right是递归出口 if(left < right){ //分 mergeSort(arr, left, mid, temp); mergeSort(arr, mid + 1, right, temp); //合 merge(arr, left, mid, right, temp); } } int main(int argc, char *argv[]) { int num, i; int *arr, *temp; scanf("%d", &num); arr = (int *)malloc(sizeof(int) * num); temp = (int *)malloc(sizeof(int) * num); for(i = 0; i < num; i++){ scanf("%d", &arr[i]); } mergeSort(arr, 0, num - 1, temp); printf("归并排序后的数组是：n"); for(i = 0; i < num; i++){ printf("%d ", arr[i]); } free(temp); free(arr); return 0; }
基数排序 / 桶排序（Radix Sort）
将所有待比较数值（正整数）统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列。
#include#include //基数（桶）排序 void radixSort(int* arr, int num){ //记录最大数组中最大的元素 和 最大数的位数 int max, maxLength = 0; int i, j, n, k, index = 0; //循环变量 int digitOfElement; //每个元素相应位数的值 //定义一个二维数组，表示10个桶，每个桶就是一个一维数组 //说明： //（1）二维数组包含10个一维数组 分别表示位数对应 0，1，2，3，4，5，6，7，8，9 //（2）为了防止在放入元素的时候数据溢出，每个一维数组（桶），大小定义为num //（3）基数排序是使用空间换时间的经典算法 int bucket[10][num]; //为了记录每个桶中实际放了多少个数据，定义一个一维数组记录各个桶每次放入数据的个数 //bucketElementCounts[i] 分别表示位数对应 0，1，2，3，4，5，6，7，8，9 int bucketElementCounts[10] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0}; //找到数组中最大数的位数 max = arr[0]; //基准数据 for(i = 1; i < num; i++){ if(arr[i] > max){ max = arr[i]; } } //得到最大数的位数 do{ maxLength++; max /= 10; }while(max != 0); //基数排序 //进行最大位数次排序 for(i = 0, n = 1; i < maxLength; i++, n *= 10){ for(j = 0; j < num; j++){ //取出每个元素相应位数的值 digitOfElement = arr[j] / n % 10; //放入桶中 bucket[digitOfElement][bucketElementCounts[digitOfElement]] = arr[j]; bucketElementCounts[digitOfElement]++; } index = 0; //按照桶的顺序（一维数组下标）把元素取出，放回原来的数组 //遍历每一个 桶，并将桶中的数据放入原数组 for(j = 0; j < 10; j++){ //如果桶中有数据，我们才放入 if(bucketElementCounts[j]){ //循环第j个桶 for(k = 0; k < bucketElementCounts[j]; k++){ //取出元素，index作为循环变量 arr[index++] = bucket[j][k]; } } //！每一轮处理完后，要把bucketElementCounts[j] = 0 bucketElementCounts[j] = 0; } } } int main(int argc, char *argv[]) { int num, i; int *arr; scanf("%d", &num); arr = (int *)malloc(sizeof(int) * num); for(i = 0; i < num; i++){ scanf("%d", &arr[i]); } radixSort(arr, num); printf("基数排序后的结果如下：n"); for(i = 0; i < num; i++){ printf("%d ", arr[i]); } return 0; }
