C ++快速排序算法

本文介绍了C ++快速排序算法的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

我不打算复制qsort算法。我正在练习写qsort，这是我想出来的，我对我的代码的哪部分错了感兴趣。请不要告诉我这是家庭作业，因为我可以只使用下面的链接中的代码。

I'm not looking to copy a qsort algorithm. I'm practicing writing qsort and this is what I've come up with and I'm interested in what part of my code is wrong. Please don't tell me that this is homework cause I could just use the code in the link below.

参考： http：// xoax/comp/sci/algorithms/Lesson4.php

运行时，我在控制台中看到：

When this runs I get this in the console:

Program loaded. run [Switching to process 10738] Running… Current language: auto; currently c++ Program received signal: "EXC_ARITHMETIC". void myQSort(int min, int max, int* myArray) { // Initially find a random pivot int pivotIndex = rand() % max; int pivot = myArray[pivotIndex]; int i = 0 , j = max-1; // Pointer to begining of array and one to the end int* begin = myArray; int* end = &myArray[max-1]; // While begin < end while( begin < end ) { // Find the lowest bound number to swap while( *begin < pivot ) { begin++; } while( *end > pivot ) { // Find the highest bound number to swap end--; } // Do the swap swap(begin,end); } // Partition left myQSort(0, pivotIndex-1, myArray); // Partiion right myQSort(pivotIndex+1,max, myArray); }

EDIT-- Swap代码： / p>

EDIT-- Code for Swap:

void swap(int* num, int* num2) { int temp = *num; *num = *num2; *num2 = temp; }

推荐答案

// sort interval [begin, end) void myQSort(int* begin, int* end) { if(end - begin < 2) return; int* l = begin; int* r = end - 1; // Initially find a random pivot int* pivot = l + rand() % (r - l + 1); while(l != r) { // Find the lowest bound number to swap while(*l < *pivot) ++l; while(*r >= *pivot && l < r) --r; // Do the swap if(pivot == l) { pivot = r; } std::swap(*l, *r); } // Here l == r and numbers in the interval [begin, r) are lower and in the interval [l, end) are greater or equal than the pivot // Move pivot to the position std::swap(*pivot, *l); // Sort left myQSort(begin, l); // Sort right myQSort(l + 1, end); }