1

一步一步写算法（之快速排序）

 1 year ago
source link: https://blog.51cto.com/feixiaoxing/5880371
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
neoserver,ios ssh client

一步一步写算法（之快速排序）

精选 原创

feixiaoxing 2022-11-23 10:35:19 ©著作权

文章标签 算法 null 测试 编程 c 文章分类 其它 前端开发 阅读数295

    快速排序是编程中经常使用到的一种排序方法。可是很多朋友对快速排序有畏难情绪，认为快速排序使用到了递归，是一种非常复杂的程序，其实未必如此。只要我们使用好了方法，就可以自己实现快速排序。

    首先，我们复习一下，快速排序的基本步骤是什么：

    1、 判断输入参数的合法性

    2、把数组的第一个数据作为比较的原点，比该数据小的数据排列在左边，比该数据大的数据排列在右边

    3、按照（2）的方法分别对左边的数组和右边的数据进行和（2）一样的数据排列

    那么实际编写代码中，应该怎么做呢？

    a）首先，判断数据的合法性？

void quick_sort(int array[], int length)
{
  int median = 0;
  if(NULL == array || 0 == length)
    return;

_quick_sort(array, 0, length -1);
}



b）寻找中间数，分别对左边和右边的数据进行排序 



void _quick_sort(int array[], int start, int end)
{
  int middle;
  if(start >= end)
    return;

middle = get_middle(array, start, end);
  _quick_sort(array, start, middle -1);
  _quick_sort(array, middle + 1, end);
}

void quick_sort(int array[], int length)
{
  int median = 0;
  if(NULL == array || 0 == length)
    return;

_quick_sort(array, 0, length-1);
}



c）那么这里的中间数应该怎么安排呢？ 



int get_middle(int array[], int start, int end)
{
  int front = 0;
  int tail = end - start;
  int value = array[start];
  int length = end - start + 1;
  int loop = start + 1;

while(loop <= end){
    if(array[loop] < value){
      gQuickSort[front] = array[loop];
      front ++;
    }else{
      gQuickSort[tail] = array[loop];
      tail --;
    }

loop ++;
  }

gQuickSort[front] = value;
  memmove(&array[start], gQuickSort, sizeof(int) * (length));
  return start + front ;
}



    注意：这里gQuickSort是一个全局数组，主要是为了作为排序的临时数组使用，实际环境中大家可以灵活运用各种方法。   



 d）基本的快速排序就完成了，那我们怎么测试呢？我们可以编写几个简单的测试用例？



static void test1()
{
  int array[] = {1};
  quick_sort(array, sizeof(array)/sizeof(int));
}

static void test2()
{
  int array[] = {2, 1};
  quick_sort(array, sizeof(array)/sizeof(int));
  assert(1 == array[0]);
  assert(2 == array[1]);
}

static void test3()
{
  int array[] = {4, 3, 2,1};
  quick_sort(array, sizeof(array)/sizeof(int));
  assert(1 == array[0]);
  assert(2 == array[1]);
  assert(3 == array[2]);
  assert(4 == array[3]);
}

static void test4()
{
  int array[] = {3, 2, 1};
  quick_sort(array, sizeof(array)/sizeof(int));
  assert(1 == array[0]);
  assert(2 == array[1]);
  assert(3 == array[2]);
}

        

        

            

                report
            

        

    







        
Recommend

        



                

    
About Joyk

    
 





Aggregate valuable and interesting links.

Joyk means Joy of geeK