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

嵌入式C语言之快速排序方法实现原理

article 2025/2/23 8:57:54

概述

1. 快速排序原理介绍

2 代码实现

2.1 代码功能介绍

2.2 源代码文件

3 功能测试

3.1 代码实现

3.2 测试

概述

本文主要介绍嵌入式C语言之快速排序方法实现原理，并编写源代码实现了快速排序的功能，并编写测试代码验证该函数的功能。

1. 快速排序原理介绍

快速排序的核心思想是分治法，其目的是将一个大的问题划分成若干小的问题，通过采取函数递归的方式以实现数值的快速排序。

具体事项步骤如下：

1）选择数组中的元素e作为分割元素，然后重新排列数组，其排列要求如下：

1）数据 value <= e: 排列在一边

2）数据 value >= e: 排列在另一边

举一个例子：

取第一个数据 e = 12, 经过第一次循环后，数据如下：

原始数据： 12 5 8 1 6 4 7 3 9 20 0 10

排序后的数组： 10 5 8 1 6 4 7 3 9 0 12 20

2）通过递归的方法调用快速方法，对从1 ~ i+1的元素进行排序

3）通过递归的方法调用快速方法，对从i+ ~n的元素进行排序

完成以上步骤之后，i左边的数据都小余或者等于e, 右边的数据都大于或者等于e。

2 代码实现

2.1 代码功能介绍

代码22行：将index = low 位置的元素作为分割点

代码27~30行：从最高index位找大于index = low位置的元素

代码34行：保存当前大于index = low位置的元素

代码38~41行：从index+1的位置开始找大于index = low位置的元素

代码46行：保存当前小于index = low位置的元素

代码49行：保存分割点的值

代码61行：分割当前数组

代码62行：调用当前函数的递归函数，重新进行排序，排序范围： low ~ middle -1

代码63行：调用当前函数的递归函数，重新进行排序，排序范围： middle +1 ~ high

2.2 源代码文件

int split( int buff[], int low, int high )
{
    int part_element = buff[low]; 
    
    for (;;)
    {
        // 将小的数据移动到左边 
        while( low < high && part_element <= buff[high] )
        {
            high--;
        }
        
        if( low >= high )
            break;
        buff[low++] = buff[high];
        
        
        // 将大的数据移动到右边 
        while( low < high && buff[low] <= part_element )
        {
            low++;
        }
        
        if( low >= high )
            break;
        
        buff[high--] = buff[low];
    }
    
     buff[high] = part_element;
    
     return high;
}

void quicksort( int buff[], int low, int high )
{
    int middle;
    
    if( low >= high)
        return;
    
    middle = split( buff, low, high );
    quicksort( buff, low, middle-1);
    quicksort( buff, middle+1, high);
}

3 功能测试

3.1 代码实现

定义一个数组，对其进行快速排序，以验证快速排序的算法功能。

代码68~69行：定义一个测试数组

代码71~78行：定义打印log函数

代码80~97行：测试排序函数的功能

源代码文件：

#define LEN      12
int t_buff[LEN] = {5,11,8,1,6,4,7,15,9,3,0,10};

void printf_log( int buff[], int len )
{
    for ( int i = 0; i <LEN; i++ )
    {
       printf("%d ", buff[i]);
    }
    printf("\r\n");
}

void test_sort( void )
{
    int high;
    int len = LEN-1; 
    
    printf_log( t_buff, len);
    printf("\r\n");
    
    high = split( t_buff, 0, len);
    printf_log( t_buff, len);
    printf("\r\n");
    
    printf("high = %d \r\n", len);
    
    quicksort(t_buff, 0, len);
    printf_log( t_buff, len);
    printf("\r\n");
}