Сортировка массивов - классическая тема теории алгоритмов. Самые известные методы сортировки массива чисел приведены ниже. #include <stdio.h> #include <stdlib.h> #include <math.h> #include <time.h> #include <string.h> const int N = 33; void swap(int &x, int &y) { int z=x; x=y; y=z; } int randRange(int lower,int upper) { return rand() % (upper-lower+1) + lower; } void showArray(int *a) { for(int i=0;i<N;i++) { printf("%2d ",*(a+i)); } printf("\n"); } // Алгоритм вставки - slowest void sortInsertion(int *a) { for(int i=1;i<N;i++) { int tmp = a[i]; int j=i; for(j=i;j>0;j--) { if (a[j-1]>tmp) a[j]=a[j-1]; else break; } a[j]=tmp; } } // Алгоритм пузырька void sortBubble(int *a) { int limit = N-1; int leftPos = 0; do { leftPos = 0; for(int i=0;i<limit;i++) { if (a[i]>a[i+1]) { swap(a[i],a[i+1]); leftPos = i; } } limit = leftPos; } while (leftPos); } // Алгоритм кучи void sortHeapUp(int maxLevel, int *a) { int i=maxLevel; while(i!=0) { int parent = i/2; if (a[i]>a[parent]) { swap(a[i],a[parent]); i = parent; } else break; } } void sortHeapDown(int maxLevel, int *a) { int i = 0; for(;;) { int child = 2*i; if (child>maxLevel) break; if (child+1 <= maxLevel) { if (a[child+1]>a[child]) child+=1; } if (a[i]<a[child]) { swap(a[i],a[child]); i = child; } else break; } } void sortHeap(int *a) { for(int i=1;i<N;i++) { sortHeapUp(i,a); } for(int i=N-1;i>0;i--) { swap(a[0],a[i]); sortHeapDown(i-1,a); } } // Алгоритм обмена void sortExchange(int *a) { for(int i=0;i<N;i++) { int smallest = i; for(int j=i+1;j<N;j++) { if (a[j]<a[smallest]) smallest=j; } if (smallest>i) swap(a[i],a[smallest]); } } // Алгоритм ракушки void sortShell(int *a) { for(int offset = N/2; offset>0; offset/=2) { int maxPos; int limit=N-offset; do { maxPos = 0; for(int i=0;i<limit;i++) { if (a[i]>a[i+offset]) { swap(a[i],a[i+offset]); maxPos = i; } } limit = maxPos-offset; } while(maxPos); } } // Алгоритм быстрой сортировки - fastest void sortQuick(int low, int high, int *a) { if (low<high) { if ((high-low)==1) { if (a[low]>a[high]) swap(a[low],a[high]); } else { int randIndex = randRange(low,high); swap(a[low],a[randIndex]); int part = a[high]; int i,j; do { i=low; j=high; while (i<j && a[i]<=part) i++; while (j>i && a[j]>=part) j--; if (i<j) swap(a[i],a[j]); } while(i<j); swap(a[i],a[high]); if ((i-low)<(high-i)) { sortQuick(low,i-1,a); sortQuick(i+1,high,a); } else { sortQuick(i+1,high,a); sortQuick(low,i-1,a); } } } } int main() { srand(time(NULL)); int list[N]; int save[N]; for(int i=0;i<N;i++) { list[i] = rand() % 100; } // save original array memcpy(save,list,sizeof(int)*N); showArray(list); sortInsertion(list); showArray(list); // restore original array memcpy(list,save,sizeof(int)*N); sortBubble(list); showArray(list); memcpy(list,save,sizeof(int)*N); sortHeap(list); showArray(list); memcpy(list,save,sizeof(int)*N); sortExchange(list); showArray(list); memcpy(list,save,sizeof(int)*N); sortShell(list); showArray(list); memcpy(list,save,sizeof(int)*N); sortQuick(0, N-1, list); showArray(list); return 1; } Есть также варианты на Паскале: uses crt; const N=20; type TArray = array [1..N] of integer; procedure show_array(a:TArray); var i: integer; begin for i:=1 to N do write(a[i]:4); writeln; end; procedure random_array(var a:TArray); var i: integer; begin for i:=1 to N do a[i]:=random(100); end; procedure swap(var a,b:integer); var c:integer; begin c:=a; a:=b; b:=c; end; procedure BubleSort(var a:TArray); var i,count:integer; noswap:boolean; begin count:=0; repeat noswap:=true; for i:=1 to N-1 do if a[i]>a[i+1] then begin swap(a[i],a[i+1]); count:=count+1; noswap:=false; end; until noswap; writeln('Count: ',count); end; procedure QuickBubleSort(var a:TArray); var i,j,count:integer; begin count:=0; for i:=1 to N-1 do for j:=i+1 to N do if a[j]<a[i] then begin swap(a[i],a[j]); count:=count+1; end; writeln('Count: ',count); end; procedure InsertSort(var a:TArray); var i,j,k,count:integer; begin count:=0; for i:=1 to N-1 do begin k:=i; for j:=i+1 to N do if a[k]>a[j] then begin k:=j; count:=count+1; end; swap(a[k], a[i]); end; writeln('Count: ',count); end; procedure QuickSort(var a:TArray; first,last:integer; var count: integer); var l,r:integer; begin l:=first; r:=last; repeat while (a[l]<=a[r]) and (l<r) do r:=r-1; if l<r then begin swap(a[l],a[r]); l:=l+1; count:=count+1; end; while (a[l]<=a[r]) and (l<r) do l:=l+1; if l<r then begin swap(a[l],a[r]); r:=r-1; count:=count+1; end; until l=r; if l-1>first then QuickSort(a,first,l-1,count); if last>r+1 then QuickSort(a,r+1,last,count); end; procedure MixSort(var a:TArray; first,last:integer; var count: integer); var l,r,x:integer; begin l:=first; r:=last; x:=a[(l+r) div 2]; repeat while a[l]<x do l:=l+1; while x<a[r] do r:=r-1; if l<=r then begin swap(a[l],a[r]); l:=l+1; r:=r-1; count:=count+1; end; until l>r; if first<r then MixSort(a,first,r,count); if l<last then MixSort(a,l,last,count); end; var a,b: TArray; c:integer; begin clrscr; randomize; random_array(a); show_array(a); b:=a; BubleSort(a); show_array(a); a:=b; QuickBubleSort(a); show_array(a); a:=b; InsertSort(a); show_array(a); a:=b; c:=0; QuickSort(a,1,N,c); writeln('Count: ',c); show_array(a); a:=b; c:=0; MixSort(a,1,N,c); writeln('Count: ',c); show_array(a); readkey; end.
Справочник алгоритмов v0.05 © 2007-2025 Igor Salnikov aka SunDoctor