1.快速排序
关于快速排序的逻辑原理是这样的：
将两个指针i，j分别指向表的起始和最后的位置，T为临时变量。
反复操作以下两步：
（1）j逐渐减小，并逐次比较j指向的元素和目标元素的大小，若p(j)<T则交换位置。
（2）i逐渐增大，并逐次比较i指向的元素和目标元素的大小，若p(i)>T则交换位置。
直到i，j指向同一个值，循环结束。
下面是源码
#include <stdio.h> #include <stdlib.h> void swap(int A[],int i,int j) { int temp=0; if(A[i]>A[j]) { temp=A[j]; A[j]=A[i]; A[i]=temp; } } /* 快速排序 */ void quick_sort(int x[],int left, int right) { int temp = left; int i; if (left >= right) return; for (i = left+1; i<= right; i++) { if(x[i] < x[left]) swap(x, ++temp, i); } swap(x, left, temp); quick_sort(x,left, temp-1); quick_sort(x,temp+1, right); } int main() { int number[]={10,9,8,7,6,5,4,3,2,1}; int i=0,len; printf("start ....\n"); len=(int)sizeof(number)/sizeof(*number); printf("len =%d\n",len); quick_sort(number,0,9); for(i=0;i<10;i++) { printf("%d ",number[i] ); } printf("\n"); printf("end ....\n"); exit(0); }
代码已经编译调试过了，亲测可行。
2.插入排序
#include <stdlib.h> #include <stdio.h> void printf_buf(int* buf, int size) { int i; for (i = 0; i < size; i++) printf("%d ", buf[i]); printf("\r\n"); } void insert_funs(int *buf, int size) { int cur; int i,j; for (i = 1; i < size; i++) { printf(" %d poll:\r\n",i); cur = buf[i]; for (j = i - 1; j >= 0 && buf[j] > cur; j --) { buf[j + 1] = buf[j]; } buf[j + 1] = cur; printf_buf(buf, size); } printf("\n"); } int main(int argc, char* argv) { int num[] = { 14,3,12, 10, 12,1, 5 ,16}; int i; printf("insert funs\r\n"); insert_funs(num, sizeof(num)/sizeof(num[0])); printf("\n"); return 0; }
运行：
3.冒泡排序
#include<stdio.h> #include<stdlib.h> void printf_buf(int* buf, int size) { int i; for (i = 0; i < size; i++) printf("%d ", buf[i]); printf("\r\n"); } void swap(int x[], int i, int j) { int temp = 0; if (x[i] > x[j]) { temp = x[i]; x[i] = x[j]; x[j] = temp; } } void BubbleSort(int a[], int len) { int i, j, temp; for (j = 0; j < len - 1; j++) { for (i = 0; i < len - 1 - j; i++) swap(a, i, i + 1); } } int main() { int num[] = { 20, 8, 18, 3, 30, 14, 77, 32 }; int len = sizeof(num) / sizeof(num[0]); int i = 0; printf("start:\r\n"); printf_buf(num, len); printf("\n"); BubbleSort(num, len); printf("end:\r\n"); printf_buf(num, len); printf("\n"); return 0; }
运行：
4.选择排序
原理：从所有记录中选出最小的一个数据元素与第一个位置的记录交换；然后在剩下的记录当中再找最小的与第二个位置的记录交换，循环到只剩下最后一个数据元素为止。
#include<stdio.h> #include<stdlib.h> void printf_buf(int* buf, int size) { int i; for (i = 0; i < size; i++) printf("%d ", buf[i]); printf("\r\n"); } //如果下标为i的数大于下标为j的数，交互两个数的位置 void swap(int x[], int i, int j) { int temp = 0; if (x[i] > x[j]) { temp = x[i]; x[i] = x[j]; x[j] = temp; } } void selectSort(int num[], int size) { int i, j,minindex; for (i; i < size; i++) { minindex = i; for (j = i + 1; j < size; j++) if (num[j] < num[minindex]) minindex = j; swap(num, i, minindex); } } int main() { int num[] = { 20, 8, 18, 3, 30, 14, 77, 32 }; int len = sizeof(num) / sizeof(num[0]); int i = 0; printf("start:\r\n"); printf_buf(num, len); printf("\n"); selectSort(num, len); printf("end:\r\n"); printf_buf(num, len); printf("\n"); return 0; }
运行
5.希尔排序
希尔排序就是在一个序列中进行分组（简称：增量），然后对每个分组分别进行插入排序。随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个序列恰好被分成一组，算法便终止。
简单的说希尔排序是插入排序的升级版。
#include<stdio.h> #include<stdlib.h> void printf_buf(int* buf, int size) { int i; for (i = 0; i < size; i++) printf("%d ", buf[i]); printf("\r\n"); } void shellSort(int a[], int n) { int i, j, gap; for (gap = n / 2; gap > 0; gap /= 2) { for (i = 0; i < gap; i++) { for (j = i + gap; j < n; j += gap) { if (a[j] < a[j-gap]) { int tmp = a[j];//基数 int k = j - gap;//标记分组后的下标（j的前一个数据） while (k >= 0 && a[k] > tmp)//前一个数大，就交换 { a[k+gap] = a[k]; k -= gap;//查找前一个值 } a[k + gap] = tmp; printf_buf(a, n); } } } } } int main() { int num[] = { 8, 9, 1, 7, 2,3,5,4,6,0}; int len = sizeof(num) / sizeof(num[0]); int i = 0; printf("start:\r\n"); printf_buf(num, len); printf("\n"); shellSort(num, len); printf("end:\r\n"); printf_buf(num, len); printf("\n"); return 0; }
