排序算法经典集锦(C、C#).doc

名称：直接插入排序 稳定的排序思想：每次从无序表中取出第一个元素，把它插入到有序表的合适位置，使有序 表仍然有序时间复杂度：0（n2）实现语言：C语言编译环境：TC 3.0#include /*标准输入输出头文件*/#include/*标准库头文件*/void Insert_Sort(int *arr, int len) int i,j,temp; for(i=1;i=0 & temp*(arr+j);j-) *(arr+j+1)=*(arr+j);/后移*(arr+j+1)=temp; /插入到正确位置 int main() int i,array10; randomize(); /初始化随机数发生器，该函数定义在库文件中 for(i=0;i10;i+)arrayi=rand()%100; /rand：伪随机数发生器，获取0到99的随机数 Insert_Sort(array,10); printf(The result is:); for(i=0;i10;i+)printf(%d ,arrayi); return 0;名称：直接插入排序实现语言：C语言编译环境：VS2010using System;using System.Collections.Generic;class Program static void Main(string args) Random rand = new Random(); int array = new int10; for (int i = 0; i 10; i+) arrayi = rand.Next(100); Insertion_Sort(array); Console.WriteLine(随机生成10个数（099）并排序输出为：); foreach (int item in array) Console.Write(item); Console.Write( ); Console.ReadKey(); static void Insertion_Sort(int arr) int i,j,temp; for (i = arr.GetLowerBound(0) + 1; i = 0 & arrj temp; j-) arrj + 1 = arrj; arrj + 1 = temp; 名称：希尔排序（缩小增量排序）不稳定的排序思想：将整个待排序记录序列分割成为若干个子序列分别进行直接插入排序，待整个序列中 的记录“基本有序“时，再对全体记录进行一次直接插入排序时间复杂度：0（nlogn） 0（n2）实现语言：C语言编译环境：TC 3.0#include #include void Shell_Sort(int *arr, int len) int i,j,h,temp; for(h=len/2;h0;h/=2) /*控制增量*/ for(i=h;i=0 & temp*(arr+j);j-=h) *(arr+j+h)=*(arr+j); *(arr+j+h)=temp; int main()int i,array10;randomize(); for(i=0;i10;i+)arrayi=rand()%100; Shell_Sort(array,10); printf(The result is:); for(i=0;i10;i+) printf(%d ,arrayi); return 0;名称：希尔排序（缩小增量排序）实现语言：C语言编译环境：VS2010using System;using System.Collections.Generic;class Program static void Main(string args) Random rand = new Random(); int array = new int10; for (int i = 0; i 0; h /= 2) for (i = h; i = 0 & temp arrj; j -= h) arrj + h = arrj; arrj + h = temp; 名称：冒泡排序 稳定的排序思想：依次比较相邻的两个数，将小数放在前面，大数放在后面，一趟排序 结束后，最大的数到了最后；依次循环N趟时间复杂度：0（n2）实现语言：C语言编译环境：TC 3.0#include #include#define TRUE 1#define FALSE 0void Swap(int *x,int *y) *x+=*y; *y=*x-*y; *x=*x-*y;void Bubble_Sort(int a,int len) int i,j,change; for(i=len-1,change=TRUE;i0 & change;-i) change=FALSE; for(j=0;jaj+1) Swap(&aj,&aj+1); change=TRUE; int main() int i,array10;randomize(); for(i=0;i10;i+)arrayi=rand()%100; Bubble_Sort(array,10); printf(The result is:); for(i=0;i10;i+)printf(%d ,arrayi); return 0; 名称：冒泡排序实现语言：C语言编译环境：VS2010using System;using System.Collections.Generic;class Program static void Main(string args) Random rand = new Random(); int array = new int10; for (int i = 0; i 10; i+) arrayi = rand.Next(100); Bubble_Sort(array); Console.WriteLine(随机生成10个数（099）并排序输出为：); foreach (int item in array) Console.Write(item);Console.Write( ); Console.ReadKey(); static void Swap(ref T x, ref T y) T temp = default(T); temp = x;x = y;y = temp; static void Bubble_Sort(int arr) bool change = true; for (int i = arr.GetUpperBound(0); i arr.GetLowerBound(0) & change; -i) change = false; for (int j =arr.GetLowerBound(0); j arrj + 1) Swap(ref arrj, ref arrj + 1);change = true; 名称：快速排序（对冒泡排序的改进）不稳定的排序思想：通过一趟排序将待排序记录分割成独立的两部分，其中一部分记录的 关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续 进行排序，以达到整个序列有序。时间复杂度：0（nlogn）0（n2）实现语言：C语言编译环境：TC 3.0#include #include int Partition(int *arr,int low,int high) int temp=*(arr+low); /用子表的第一个记录作枢轴记录 while(lowhigh) /从表的两端交替向中间扫描 while(low=temp) -high; *(arr+low)=*(arr+high); /将比枢轴记录小的交换到低端 while(lowhigh & *(arr+low)=temp) +low; *(arr+high)=*(arr+low); /将比枢轴记录大的交换到高端 *(arr+low)=temp; return low;void Quick_Sort(int arr,int low,int high) if(lowhigh) int flag=Partition(arr,low,high); Quick_Sort(arr,low,flag-1);Quick_Sort(arr,flag+1,high); int main()int i,array10;randomize(); for(i=0;i10;i+)arrayi=rand()%100; Quick_Sort(array,0,9);printf(The result is:);for(i=0;i10;i+)printf(%d ,arrayi);return 0;名称：快速排序（对冒泡排序的改进）实现语言：C语言编译环境：VS2010using System;using System.Collections.Generic;class Program static void Main(string args) Random rand = new Random(); int array = new int10; for (int i = 0; i 10; i+) arrayi = rand.Next(100); Quick_Sort(array, 0, 9); Console.WriteLine(随机生成10个数（099）并排序输出为：); foreach (int item in array) Console.Write(item); Console.Write( ); Console.ReadKey(); static void Quick_Sort(int arr, int low, int high) if (low high) int flag = Partition(arr, low, high); Quick_Sort(arr, low, flag - 1); Quick_Sort(arr, flag + 1, high); static int Partition(int arr, int low, int high) int temp = arrlow; while (low high) while(low = temp) -high; arrlow = arrhigh; while(low high & arrlow = temp) +low; arrhigh = arrlow; arrlow = temp; return low; 名称：交换排序思想：根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置时间复杂度：0（n2）实现语言：C语言编译环境：TC 3.0#include #includevoid Swap(int *x,int *y) *x+=*y; *y=*x-*y; *x=*x-*y;void Swap_Sort(int arr,int len) int i,j; for(i=0;ilen;i+) for(j=i+1;jlen;j+) if(arrjarri) Swap(&arri,&arrj); int main()int i,array10;randomize(); for(i=0;i10;i+)arrayi=rand()%100; Swap_Sort(array,10); printf(The result is:); for(i=0;i10;i+)printf(%d ,arrayi); return 0;名称：交换排序实现语言：C语言编译环境：VS2010using System;using System.Collections.Generic;class Program static void Main(string args) Random rand = new Random(); int array = new int10; for (int i = 0; i 10; i+) arrayi = rand.Next(100); Swap_Sort(array); Console.WriteLine(随机生成10个数（099）并排序输出为：); foreach (int item in array) Console.Write(item); Console.Write( ); Console.ReadKey(); static void Swap(ref T x, ref T y) T temp = default(T); temp = x;x = y;y = temp; static void Swap_Sort(int arr) for (int i = arr.GetLowerBound(0); i = arr.GetUpperBound(0); i+) for (int j = i + 1; j = arr.GetUpperBound(0); j+) if (arrj arri) Swap(ref arri, ref arrj); 名称：选择排序思想：每一趟从待排序的数据元素中选出最小（或最大）的一个元素，顺序放在 已排好序的数列的最后，直到全部待排序的数据元素排完时间复杂度：0（n2）实现语言：C语言编译环境：TC 3.0#include#includevoid Swap(int *x,int *y) *x+=*y; *y=*x-*y; *x=*x-*y;void Selection_Sort(int a,int len) int i,j,index; for(i=0;ilen;i+) index=i;for(j=i+1;jlen;j+) if(ajaindex)index=j; if(i!=index)Swap(&ai,&aindex); int main() int i,array10; randomize(); for(i=0;i10;i+)arrayi=rand()%100; selection_Sort(array,10); printf(The result is:); for(i=0;i10;i+)printf(%d ,arrayi); return 0;名称：选择排序实现语言：C语言编译环境：VS2010using System;using System.Collections.Generic;class Program static void Main(string args) Random rand = new Random(); int array = new int10; for (int i = 0; i 10; i+) arrayi = rand.Next(100); Selection_Sort(array); Console.WriteLine(随机生成10个数（099）并排序输出为：); foreach (int item in array) Console.Write(item);Console.Write( ); Console.ReadKey(); static void Swap(ref T x, ref T y) T temp = default(T); temp = x;x = y; y= temp; static void Selection_Sort(int arr) int index; for (int i = arr.GetLowerBound(0); i = arr.GetUpperBound(0); i+) index = i; for (int j = i + 1; j = arr.GetUpperBound(0); j+) if (arrj arrindex) index = j; if(index!=i) Swap(ref arri, ref arrindex); 名称：归并排序思想：将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列时间复杂度：0（nlogn）实现语言：C语言编译环境：TC 3.0#include #include void Merge(int *arr, int p, int q, int r) int begin1,end1,begin2,end2,i=0,count=0; int *temp=(int*)malloc(sizeof(int)*(r-p+1); if(!temp) return; begin1 = p;end1 = q;begin2 = q+1;end2 = r; while (begin1=end1 & begin2=end2) if(*(arr+begin1) *(arr+begin2) tempcount+ = *(arr+begin1+); else tempcount+ = *(arr+begin2+); while(begin1 = end1) tempcount+ = *(arr+begin1+); while (begin2 = end2) tempcount+ = *(arr+begin2+); for (i=0;icount;i+) *(arr+p+i) = tempi; free(temp);void Merge_Sort(int arr, int first, int last) int mid; if (firstlast)mid = (first+last)/2;Merge_Sort(arr, first, mid);Merge_Sort(arr, mid+1, last);Merge(arr, first, mid, last);int main() int i,array10; randomize(); for(i=0;i10;i+)arrayi=rand()%100; Merge_Sort(array,0,9); printf(The result is:); for(i=0;i10;i+)printf(%d ,arrayi); return 0;名称：归并排序实现语言：C语言编译环境：VS2010using System;using System.Collections.Generic;class Program static void Main(string args) Random rand = new Random(); int array = new int10; for (int i = 0; i 10; i+) arrayi = rand.Next(100); Merge_Sort(array); Console.WriteLine(随机生成10个数（099）并排序输出为：); foreach (int item in array) Console.Write(item); Console.Write( ); Console.ReadKey(); static void Merge_Sort(int arr) Merge_Sort(arr, 0, arr.Length - 1); static void Merge_Sort(int arr, int start, int end) if (start end) int mid = (start + end) / 2;Merge_Sort(arr, start, mid); Merge_Sort(arr, mid + 1, end); Merge_Sort(arr, start, mid, end); static void Merge_Sort(int arr, int start, int middle, int end) int i = start, j = middle + 1, k = 0; int temp = new intend - start + 1; while (i = middle & j = end) if (arri arrj) tempk+ = arri+; else tempk+ = arrj+; while (i = middle) tempk+ = arri+; while (j = end) tempk+ = arrj+; i = start; foreach (var item in temp) arri+ = item; 名称：堆排序思想：利用堆积树（堆）这种资料结构所设计的一种排序算法时间复杂度：=0（nlogn）实现语言：C语言编译环境：TC 3.0#include#includevoid Swap(int *x,int *y) *x+=*y;*y=*x-*y;*x=*x-*y; void HeapAdjust(int *arr,int p,int len) /构造大顶堆 int i,temp=*(arr+p); for(i=2*p;ilen;i=i*2) if(ilen-1 & *(arr+i)=*(arr+i) break;*(arr+p)=*(arr+i);p=i; *(arr+p)=temp;void Heap_Sort(int *arr,int len) int i; for(i=len/2;i=0;-i)HeapAdjust(arr,i,len); for(i=len-1;i0;-i) Swap(&*