快速排序
``` #include <stdio.h> #include <stdlib.h> #include <stdbool.h> #include <malloc.h> /* 快速排序实现 */ int FindPos(int * a, int low, int high); void QuickSort(int * a, int low, int high); int main(void) { int a[6] = {-2, 1, 0, -985, 4, -93}; int i; QuickSort(a, 0, 5); //第二个参数表示第一个元素的下标 第三个参数表示最后一个元素的下标 for (i=0; i<6; ++i) printf("%d ", a[i]); printf("\n"); return 0; } void QuickSort(int * a, int low, int high) { int pos; if (low < high) { pos = FindPos(a, low, high); QuickSort(a, low, pos-1); QuickSort(a, pos+1, high); } } int FindPos(int * a, int low, int high) { int val = a[low]; while (low < high) { while (low<high && a[high]>=val) --high; a[low] = a[high]; while (low<high && a[low]<=val) ++low; a[high] = a[low]; }//终止while循环之后low和high一定是相等的 a[low] = val; return high; //high可以改为low, 但不能改为val 也不能改为a[low] 也不能改为a[high] } ```
冒泡排序
``` #include <stdio.h> #include <stdlib.h> #include <stdbool.h> #include <malloc.h> /* 冒泡排序实现 */ int main() { int i=0,j=0,len=0,t=0; int a[5]={1,10,50,30,61}; len=sizeof(a)/ sizeof(a[0]); for(i=0;i<len-1;i++){ for(j=0;j<len-1-i;j++){ if(a[j]>a[j+1]){ t=a[j]; a[j]=a[j+1]; a[j+1]=t; } } } printf("冒泡排序后的数据为:"); for(i=0;i<len;i++){ printf("%d ",a[i]); } } ```
插入排序
``` #include <stdio.h> #include <stdlib.h> #include <stdbool.h> #include <malloc.h> /* 插入排序实现 */ void InsertionSort(int *num,int n); int main() { int i=0,len=0; int a[5]= {1,10,50,30,61}; len=sizeof(a)/ sizeof(a[0]); InsertionSort(a,len); printf("插入排序后的数据为:"); for(i=0; i<len; i++) { printf("%d ",a[i]); } } void InsertionSort(int *num,int n) { int i = 0; int j = 0; int tmp = 0; for(i = 1; i<n; i++) { tmp = num[i];//从待插入组取出第一个元素。 j = i-1; //i-1即为有序组最后一个元素(与待插入元素相邻)的下标 while(j>=0&&tmp<num[j]) //注意判断条件为两个,j>=0对其进行边界限制。第二个为插入判断条件 { num[j+1] = num[j];//若不是合适位置,有序组元素向后移动 j--; } num[j+1] = tmp;//找到合适位置,将元素插入。 } } ```
选择排序
``` #include <stdio.h> #include <stdlib.h> #include <stdbool.h> #include <malloc.h> /* 选择排序实现 */ int main() { int a[6] = {-2, 1, 0, -985, 4, -93}; int len=sizeof(a)/ sizeof(a[0]); for(int i=0;i<len;i++){ int min = i;//最小元素的下标 for(int j=i+1;j<len;j++){ if(a[j]<a[min]){ min = j; } } int temp = a[i]; a[i]=a[min]; a[min] = temp; } printf("选择排序后的数据为:"); for(int i=0;i<len;i++){ printf("%d ",a[i]); } } ```
归并排序
``` #include <stdio.h> #include <stdlib.h> #include <stdbool.h> #include <malloc.h> #define Max_ 10 // 打印结果 void Show(int arr[], int n) { int i; for ( i=0; i<n; i++ ) printf("%d ", arr[i]); printf("\n"); } // 归并排序中的合并算法 void Merge(int array[], int left, int m, int right) { int aux[Max_] = {0}; // 临时数组 (若不使用临时数组,将两个有序数组合并为一个有序数组比较麻烦) int i; //第一个数组索引 int j; //第二个数组索引 int k; //临时数组索引 for (i = left, j = m+1, k = 0; k <= right-left; k++) // 分别将 i, j, k 指向各自数组的首部。 { //若 i 到达第一个数组的尾部,将第二个数组余下元素复制到 临时数组中 if (i == m+1) { aux[k] = array[j++]; continue; } //若 j 到达第二个数组的尾部,将第一个数组余下元素复制到 临时数组中 if (j == right+1) { aux[k] = array[i++]; continue; } //如果第一个数组的当前元素 比 第二个数组的当前元素小,将 第一个数组的当前元素复制到 临时数组中 if (array[i] < array[j]) { aux[k] = array[i++]; } //如果第二个数组的当前元素 比 第一个数组的当前元素小,将 第二个数组的当前元素复制到 临时数组中 else { aux[k] = array[j++]; } } //将有序的临时数组 元素 刷回 被排序的数组 array 中, //i = left , 被排序的数组array 的起始位置 //j = 0, 临时数组的起始位置 for (i = left, j = 0; i <= right; i++, j++) { array[i] = aux[j]; } } // 归并排序 void MergeSort(int array[], int start, int end) { if (start < end) { int i; i = (end + start) / 2; // 对前半部分进行排序 MergeSort(array, start, i); // 对后半部分进行排序 MergeSort(array, i + 1, end); // 合并前后两部分 Merge(array, start, i, end); } } int main() { //测试数据 int arr_test[Max_] = { 8, 4, 2, 3, 5, 1, 6, 9, 0, 7 }; //排序前数组序列 Show( arr_test, Max_ ); MergeSort( arr_test, 0, Max_-1 ); //排序后数组序列 Show( arr_test, Max_ ); return 0; } ```
希尔排序
``` void ShellSort(SqList *L)//下标0不存储元素,暂时存储元素使用 { int i,j; int increment=L->length;//增量值 do { increment=increment/3+1; /*增量序列*/ for( i=increment+1; i<=L->length; i++ ) { if (L->r[i]<L->r[i-increment]) { /*需将L->r[i]插入有序增量子表*/ L->r[0]=L->r[i];/*暂存在L->r[0] */ for (j=i-increment; j>0&&L->r[0]<L->r[j]; j-=increment) { L->r[j+increment]=L->r[j];/*记录后移,查找插入位置*/ } L->r[j+increment]=L->r[0]; /*插入*/ } } } while (increment>1); } ```
堆排序
``` package sortdemo; import java.util.Arrays; /** * 堆排序demo */ public class HeapSort { public static void main(String []args){ int []arr = {9,8,7,6,5,4,3,2,1}; sort(arr); System.out.println(Arrays.toString(arr)); } public static void sort(int []arr){ //1.构建大顶堆 for(int i=arr.length/2-1;i>=0;i--){ //从第一个非叶子结点从下至上,从右至左调整结构 adjustHeap(arr,i,arr.length); } //2.调整堆结构+交换堆顶元素与末尾元素 for(int j=arr.length-1;j>0;j--){ swap(arr,0,j);//将堆顶元素与末尾元素进行交换 adjustHeap(arr,0,j);//重新对堆进行调整 } } /** * 调整大顶堆(仅是调整过程,建立在大顶堆已构建的基础上) * @param arr * @param i * @param length */ public static void adjustHeap(int []arr,int i,int length){ int temp = arr[i];//先取出当前元素i for(int k=i*2+1;k<length;k=k*2+1){//从i结点的左子结点开始,也就是2i+1处开始 if(k+1<length && arr[k]<arr[k+1]){//如果左子结点小于右子结点,k指向右子结点 k++; } if(arr[k] >temp){//如果子节点大于父节点,将子节点值赋给父节点(不用进行交换) arr[i] = arr[k]; i = k; }else{ break; } } arr[i] = temp;//将temp值放到最终的位置 } /** * 交换元素 * @param arr * @param a * @param b */ public static void swap(int []arr,int a ,int b){ int temp=arr[a]; arr[a] = arr[b]; arr[b] = temp; } } ```
Click here to view the copyright notice of this site(点击此处查看本站版权声明)
必须 注册 为本站用户, 登录 后才可以发表评论!