Die Beherrschung der häufig verwendeten Sortieralgorithmen kann bei der tatsächlichen Projektentwicklung viel Zeit sparen. Es gibt Unterschiede in der Ausführungseffizienz jedes Sortieralgorithmus. Diese kleinen Zeitunterschiede sind bei normalen Verbindungen möglicherweise nicht spürbar, sie sind jedoch besonders wichtig in Systemen mit relativ großen Datenmengen oder knappen Ressourcen. Im Folgenden finden Sie eine kurze Einführung in drei häufig verwendete Sortieralgorithmen und einen Vergleich ihrer Ausführungseffizienz.
Blasensortierung:
Idee: Vergleichen Sie zwei benachbarte Zahlen und verschieben Sie die kleinere Zahl nach vorne. Wenn es n Zahlen gibt, müssen n-1 Durchgänge durchgeführt werden. Vergleich, n-; Im ersten Vergleich werden 1 paarweise Vergleiche durchgeführt, im j-ten Vergleich werden n-j paarweise Vergleiche durchgeführt.
Implementierungscode:
void BublleSort (int arr [], int count)
{
int i, j, temp;
for(j=0; j<count-1; j ) /* 冒泡法要排序n-1次*/
for(i=0; i<count-j-1; i )/* 值比较大的元素沉下去后，只把剩下的元素中的最大值再沉下去就可以啦 */
{
if(arr[i]>arr[i 1])/* 把值比较大的元素沉到底 */
{
temp=arr[i 1];
arr[i 1]=arr[i];
arr[i]=temp;
}
}
}Nach dem Login kopieren
Einfügungssortierung:
Idee: Nachdem Sie das zu sortierende Array erhalten haben, teilen Sie das Array in zwei Teile, den ersten Teil des Arrays Das Element ist ein Teil, und die übrigen Elemente sind ein Teil. Vergleichen Sie es dann mit allen Elementen vor diesem Element. Wenn es kein vorheriges Element gibt, das größer als dieses Element ist, dann die Position des Elements Wenn es ein Element gibt, dessen Wert größer als dieses Element ist, dann notieren Sie seine Position, z. B. I, die Position des Elements ist k, dann werden alle Elemente von der i- bis zur k-Position um ein Bit nach hinten verschoben. und dann ist die k-Position Der Wert wird an die i-Position verschoben. Auf diese Weise wird der Ort von K gefunden. Tun Sie dies für jedes Element und Sie erhalten am Ende ein sortiertes Array.
Implementierungscode:
void InsertSort ( int arr[],int count)
{
int i,j,temp;
for(i=1; i<count; i )//数组分两个部分，从第二个数组元素开始
{
temp = arr[i];//操作当前元素，先保存在其它变量中
for(j=i-1; j>-1&&arr[j]>temp;j--)//从当前元素的上一个元素开始查找合适的位置，一直查找到首元素
{
arr[i] = arr[j];
arr[j] = temp;
}
}
}Nach dem Login kopieren
Auswahlsortierung:
Idee:
Beginnen Sie zunächst mit dem Scannen aus einer Richtung basierend auf einem Element, z. B. von Scannen Sie von links nach rechts, nehmen Sie A [0] als Benchmark, suchen Sie dann das kleinste Element von A [0] ... A [9] und tauschen Sie es gegen A [0] aus. Verschieben Sie dann seine Referenzposition um eine Position nach rechts und wiederholen Sie die obige Aktion. Verwenden Sie beispielsweise A[1] als Referenz, suchen Sie die kleinste unter A[1]~A[9] und tauschen Sie sie durch A[1] aus. . Die Sortierung endet, wenn die Basisposition zum letzten Element des Arrays verschoben wird.
Implementierungscode:
void SelectSort(int arr[], int count)
{
int i,j,min,temp;
for(i=0; i<count; i )
{
min = arr[i];//以此元素为基准
for(j=i 1; j<count; j )//从j往前的数据都是排好的，所以从j开始往下找剩下的元素中最小的
{
if(min>arr[j])//把剩下元素中最小的那个放到arr[j]中
{
temp = arr[j];
arr[j] = min;
min = temp;
}
}
}
}Nach dem Login kopieren
Effizienzvergleich:
Um seine Wirkung klarer zu sehen, wird jeder Sortieralgorithmus 10.000 Mal ausgeführt. Das Folgende ist die Hauptfunktion des Testprogramms:
#include <stdio.h>
#include<stdlib.h>
#include <sys/time.h>
#include <unistd.h>
#define MAX 6
int array[MAX];
int count = MAX;
/********创建数组，并输入元素************/
void BuildArray()
{
int a,i=0;
printf("请输入数组元素: ");
for(; i<count; i )
{
scanf("%d", &a);
array[i] = a;
}
printf("\n");
}
/**********遍历输出数组元素*************/
void Traverse(int arr[], int count)
{
int i;
printf("数组输出: ");
for(i=0; i<count; i )
printf("%d\t", arr[i]);
printf("\n");
}
void BublleSort(int arr[], int count)
{
int i,j,temp;
for(j=0; j<count-1; j ) /* 气泡法要排序n-1次*/
for(i=0; i<count-j-1; i )/* 值比较大的元素沉下去后，只把剩下的元素中的最大值再沉下去就可以啦 */
{
if(arr[i]>arr[i 1])/* 把值比较大的元素沉到底 */
{
temp=arr[i 1];
arr[i 1]=arr[i];
arr[i]=temp;
}
}
}
void InsertSort(int arr[],int count)
{
int i,j,temp;
for(i=1; i<count; i )//数组分两个部分，从第二个数组元素开始
{
temp = arr[i];//操作当前元素，先保存在其它变量中
for(j=i-1; j>-1&&arr[j]>temp;j--)//从当前元素的上一个元素开始查找合适的位置，一直查找到首元素
{
arr[i] = arr[j];
arr[j] = temp;
}
}
}
void SelectSort(int arr[], int count)
{
int i,j,min,temp;
for(i=0; i<count; i )
{
min = arr[i];//以此元素为基准
for(j=i 1; j<count; j )//从j往前的数据都是排好的，所以从j开始往下找剩下的元素中最小的
{
if(min>arr[j])//把剩下元素中最小的那个放到arr[j]中
{
temp = arr[j];
arr[j] = min;
min = temp;
}
}
}
}
int main()
{
int i;
struct timeval tv1,tv2;
struct timezone tz;
BuildArray();//创建数组
Traverse(array, count);//输出最初数组
gettimeofday(&tv1,&tz);
for(i=0;i<10000;i++)
BublleSort(array, count);//冒泡排序
gettimeofday(&tv2,&tz);
printf("%d:%d/n",tv2.tv_sec-tv1.tv_sec,tv2.tv_usec-tv1.tv_usec);
Traverse(array, count);//输出排序后的数组
gettimeofday(&tv1,&tz);
for(i=0;i<10000;i++)
InsertSort(array, count);//插入排序
gettimeofday(&tv2,&tz);
printf("%d:%d/n",tv2.tv_sec-tv1.tv_sec,tv2.tv_usec-tv1.tv_usec);
Traverse(array, count);//输出排序后的数组
gettimeofday(&tv1,&tz);
for(i=0;i<10000;i++)
SelectSort(array, count);//插入排序
gettimeofday (&tv2,&tz);
printf("%d:%d/n",tv2.tv_sec-tv1.tv_sec,tv2.tv_usec-tv1.tv_usec);
Traverse(array, count);//输出排序后的数组
return 0;
}Nach dem Login kopieren
Kompilieren: gcc –g –Wall sort_test.c –o sort_test
Ausführen: ./sort_test
Die Ergebnisse sind wie folgt:
Nach vielen Tests ist die Einfügungssortierung die schnellste.
Weitere Vergleiche der Algorithmen „Blasensortierung“, „Einfügungssortierung“ und „Auswahlsortierung“ in der Sprache C. Für verwandte Artikel beachten Sie bitte die chinesische PHP-Website!
