选择排序
#include "stdio.h"
#include "stdlib.h"
#include "string.h"void printArray01(int array[], int len)
{int i = 0;for(i=0; i<len; i++){printf("%d ", array[i]);}printf("\n");
}void swap01(int array[], int i, int j)
{int temp = array[i];array[i] = array[j];array[j] = temp;
}void SelectionSort(int array[], int len) // O(n*n)
{int i = 0;int j = 0;int k = -1;for(i=0; i<len; i++){k = i; //寻找最小元素的下标for(j=i+1; j<len; j++){if( array[j] < array[k] ) //开始寻找最小元素的下标{k = j; }}swap01(array, i, k);}
}int main11()
{//int array[] = {12, 5, 433, 253, 216, 7};int array[] = {12, 5, 433, 253};int len = sizeof(array) / sizeof(*array); printArray01(array, len);SelectionSort(array, len);printArray01(array, len);system("pause");return 0;
}插入排序
#include "stdio.h"
#include "stdlib.h"
#include "string.h"void printArray02(int array[], int len)
{int i = 0;for(i=0; i<len; i++){printf("%d ", array[i]);}printf("\n");
}
void InertionSort(int array[], int len) // O(n*n)
{int i = 0;int j = 0;int k = -1;int temp = -1;//{12, 5, 433, 253, 216, 7};for(i=1; i<len; i++){k = i; //待插入位置temp = array[k];for(j=i-1; (j>=0) && (array[j]>temp); j--){ array[j+1] = array[j]; //元素后移k = j; //k需要插入的位置}array[k] = temp;//元素插入}
}int main()
{int array[] = {12, 5, 433, 253, 216, 7};int len = sizeof(array) / sizeof(*array); printArray02(array, len);InertionSort(array, len);printArray02(array, len);system("pause");return 0;
}冒泡排序
#include "stdio.h"
#include "stdlib.h"
#include "string.h"void printfArray03(int array[], int len)
{int i = 0;for(i=0; i<len; i++){printf("%d ", array[i]);}printf("\n");
}void swap03(int array[], int i, int j)
{int temp = array[i];array[i] = array[j];array[j] = temp;
}void BubbleSort(int array[], int len) // O(n*n)
{int i = 0;int j = 0;int exchange = 1; //表明数组是否已经排好序 已经排好序为0 1表示没有排好序for(i=0; (i<len) && exchange; i++){exchange = 0;//认为已经排序完毕for(j=len-1; j>i; j--){if( array[j] < array[j-1] ){swap03(array, j, j-1);exchange = 1;//}}}
}int main()
{int array[] ={8,3,6,1};int len = sizeof(array) / sizeof(*array); printfArray03(array, len);BubbleSort(array, len);printfArray03(array, len);system("pause");return 0;
}
希尔排序
#include "stdio.h"
#include "stdlib.h"
#include "string.h"void println(int array[], int len)
{int i = 0;for(i=0; i<len; i++){printf("%d ", array[i]);}printf("\n");
}
void swap(int array[], int i, int j)
{int temp = array[i];array[i] = array[j];array[j] = temp;
}void InertionSort_ddddd(int array[], int len) // O(n*n)
{int i = 0;int j = 0;int k = -1;int temp = -1;//{12, 5, 433, 253, 216, 7};for(i=1; i<len; i++){k = i; //待插入位置temp = array[k];for(j=i-1; (j>=0) && (array[j]>temp); j--){ array[j+1] = array[j]; //元素后移k = j; //k需要插入的位置}array[k] = temp;//元素插入}
}//nlogn
void ShellSort(int array[], int len) //
{int i = 0;int j = 0;int k = -1;int temp = -1;int gap = len;do{//业界统一实验的 平均最好情况 经过若干次后，收敛为1gap = gap / 3 + 1; //gap /2345 2000 都行 //O（n 1.3）for(i=gap; i<len; i+=gap){k = i;temp = array[k];for(j=i-gap; (j>=0) && (array[j]>temp); j-=gap){array[j+gap] = array[j];k = j;}array[k] = temp;}}while( gap > 1 );}int main()
{int array[] = {12, 5, 433, 253, 216, 7};int len = sizeof(array) / sizeof(*array); println(array, len);ShellSort(array, len);println(array, len); system("pause");return 0;
}快速排序
void printArray05(int array[], int len)
{int i = 0;for(i=0; i<len; i++){printf("%d ", array[i]);}printf("\n");
}void swap5(int array[], int i, int j)
{int temp = array[i];array[i] = array[j];array[j] = temp;
}
//划分过程 第一个元素当枢轴，分成2个有效子序列
int partition(int array[], int low, int high)
{int pv = array[low];while( low < high ){while( (low < high) && (array[high] >= pv) ){high--; //比基准大，本来就在右边，所以high前移动}swap5(array, low, high);while( (low < high) && (array[low] <= pv) ){low++;}swap5(array, low, high);}//返回枢轴的位置。。。重要return low;
}//让n个元素 依此减少 减少到1个元素的时候，因为1个元素可以看成一个有序的序列void QSort2(int array[], int low, int high)
{if( low < high ){int pivot = partition(array, low, high);//对子序列1排序QSort2(array, low, pivot-1);//对子序列2排序QSort2(array, pivot+1, high);}
}void QSort(int array[], int low, int high)
{if( low < high ){int pivot = partition(array, low, high);//对子序列1排序QSort2(array, low, pivot-1);//对子序列2排序QSort2(array, pivot+1, high);}
}void QuickSort(int array[], int len) // O(n*logn)
{QSort(array, 0, len-1);
}int main()
{//int array[] = {12, 5, 433, 253, 216, 7};//int array[] = {12, 5, 433};int array[] = {12, 5};int len = sizeof(array) / sizeof(*array); printArray05(array, len);QuickSort(array, len);printArray05(array, len);system("pause");return 0;
}归并排序
#include <stdio.h>
#include <malloc.h>void printArray06(int array[], int len)
{int i = 0;for(i=0; i<len; i++){printf("%d ", array[i]);}printf("\n");
}void swap6(int array[], int i, int j)
{int temp = array[i];array[i] = array[j];array[j] = temp;
}void Merge(int src[], int des[], int low, int mid, int high) //开始 结束 开始
{int i = low; //将数组分成两个连续的 序列 （第一个序列的开始）int j = mid + 1; //第二个序列的开始int k = low; while( (i <= mid) && (j <= high) ) //将小的放到目的地中{if( src[i] < src[j] ){des[k++] = src[i++];}else{des[k++] = src[j++];}}while( i <= mid ) //若还剩几个尾部元素{des[k++] = src[i++];}while( j <= high ) //若还剩几个尾部元素{des[k++] = src[j++];}
}//每次分为两路 当只剩下一个元素时，就不需要在划分
void MSort(int src[], int des[], int low, int high, int max)
{if( low == high ) //只有一个元素，不需要归并，结果赋给des[low]{des[low] = src[low]; }else //如果多个元素，进行两路划分{int mid = (low + high) / 2;int* space = (int*)malloc(sizeof(int) * max);//递归进行两路，两路的划分 //当剩下一个元素的时，递归划分结束，然后开始merge归并操作if( space != NULL ){MSort(src, space, low, mid, max); MSort(src, space, mid+1, high, max);Merge(space, des, low, mid, high); //调用归并函数进行归并}free(space);}
}void MergeSort(int array[], int len) // O(n*logn)
{MSort(array, array, 0, len-1, len);
}int main66()
{//int array[] = {21, 25, 49, 25, 16, 8};int array[] = {21, 25};int len = sizeof(array) / sizeof(*array); printArray06(array, len);MergeSort(array, len);printArray06(array, len);system("pause");return 0;
}结束！