当前位置：首页 > article >正文

排序算法 C语言

article 2025/2/28 20:06:50

一、冒泡排序

1、实现原理：两两比相邻元素，如果它们的顺序错误就把它们交换过来，小的在前，大的在后。遍历数列的工作是重复进行的，直到没有再需要交换的元素为止。

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define MAXSIZE 10

typedef struct
{
	int r[MAXSIZE];
	int length;
}SqList;

void swap(SqList *L,int i,int j)
{
	int temp = L->r[i];
	L->r[i] = L->r[j];
	L->r[j] = temp; 
}

void BubbleSort(SqList *L)
{
	int i,j;
	for(i=0;i<L->length-1;i++)
	{
		for(j=L->length-1;j>=i;j--)//从后往前，交换次数每次减少一次
		{
			if(L->r[j] > L->r[j+1])
				swap(L,j,j+1);
		}
	}
}

int main(void)
{
	int i;
	//为结构体指针的数组赋值，需要确保结构体指针已经被正确的分配了内存
	SqList *test = (SqList *)malloc(sizeof(SqList));
	if(test == NULL)
	{
		printf("内存分配失败\r\n");
	}
	test->length = sizeof(test->r)/sizeof(test->r[0]);
	printf("length:%d\r\n",test->length);

	int arry[10] = {2,5,4,1,8,9,0,3,6,7};
	memcpy(test->r,arry,test->length * sizeof(int));
	BubbleSort(test);
	for(i=0;i<10;i++)
	{
		printf("  r[%d]:%d",i,test->r[i]);
	}

	free(test);
	return 0;
}

二、简单选择排序

1、它的基本思想是：每一轮从未排序的部分中选择最小（或最大）的元素，将其与未排序部分的第一个元素交换位置，从而将最小（或最大）的元素放到已排序部分的末尾。这样，每一轮过后，未排序部分就减少一个元素，直到所有元素都排序完成。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAXSIZE 10

typedef struct
{
        int r[MAXSIZE];
        int length;
}SqList;


void swap(SqList *L,int i,int j)
{
        int temp = L->r[i];
        L->r[i] = L->r[j];
        L->r[j] = temp;
}

void SelectSort(SqList *L)
{
        int i,j,min;
        for(i=0;i<L->length-1;i++)
        {
		    min = i;
            for(j=L->length-1;j>=i;j--) //交换次数每次减少一次
            {
                if(L->r[min] > L->r[j])
                    min = j;
            }
		    if(min != i) 
		    {
			    swap(L,i,min);
		    }
        }
}


int main(void)
{
        int i;
        //为结构体指针的数组赋值，需要确保结构体指针已经被正确的分配了内存
        SqList *test = (SqList *)malloc(sizeof(SqList));
        if(test == NULL)
        {
                printf("内存分配失败\r\n");
        }

        test->length = sizeof(test->r)/sizeof(test->r[0]);
        printf("length:%d\r\n",test->length);

        int arry[10] = {2,5,4,1,8,9,0,3,6,7};
        memcpy(test->r,arry,test->length * sizeof(int));

        SelectSort(test);
        for(i=0;i<10;i++)
        {
                printf("  r[%d]:%d",i,test->r[i]);
        }

        free(test);
        return 0;
}

三、直接插入排序

1、基本思想：它的基本思想是将一个待排序的元素，按其大小插入到已经排好序的有序序列中的适当位置，从而得到一个新的、记录数增加1的有序序列

从第一个元素开始，认为该元素已经被排序。
取出下一个元素，在已经排序的元素序列中从后向前扫描。
如果已排序的元素大于新元素，将该元素移到下一位置。
重复步骤3，直到找到已排序的元素小于或等于新元素的位置。
将新元素插入到该位置后。
重复步骤2至5，直到所有元素都被排序。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAXSIZE 10

typedef struct
{
        int r[MAXSIZE];
        int length;
}SqList;

void InsertSort(SqList *L)
{
        int i,j,temp;
        for(i=1;i<L->length;i++)
        {
		    if(L->r[i] < L->r[i-1])
		    {
                temp = L->r[i];
                for(j=i-1;L->r[j]>temp;j--) 
                    L->r[j+1] = L->r[j];
			    L->r[j+1] = temp;
		    }
     	}
}

int main(void)
{
        int i;
        //为结构体指针的数组赋值，需要确保结构体指针已经被正确的分配了内存
        SqList *test = (SqList *)malloc(sizeof(SqList));
        if(test == NULL)
        {
                printf("内存分配失败\r\n");
        }
        test->length = sizeof(test->r)/sizeof(test->r[0]);
        printf("length:%d\r\n",test->length);

        int arry[10] = {2,5,4,1,8,9,0,3,6,7};
        memcpy(test->r,arry,test->length * sizeof(int));

        InsertSort(test);
        for(i=0;i<10;i++)
        {
                printf("  r[%d]:%d",i,test->r[i]);
        }

        free(test);
        return 0;
}

查看全文

http://www.kler.cn/a/488068.html