golang_算法:快速排序算法

<svg xmlns="http://www.w3.org/2000/svg" style="display: none;"><path stroke-linecap="round" d="M5,0 0,2.5 5,5z" id="raphael-marker-block" style="-webkit-tap-highlight-color: rgba(0, 0, 0, 0);"/></svg><pre><code class="lang-go hljs"><span class="token keyword">package</span> main <span class="token keyword">import</span> <span class="token string">"fmt"</span> <span class="token comment">//快速排序的基本思想：</span> <span class="token comment">//先选出一个参考值，通过一趟排序将数据分割成独立的两部分，</span> <span class="token comment">//其中一部分的所有数据都比参考值小并在参考值左侧，另外一部分的所有数据都比参考值大并在参考值右侧。</span> <span class="token comment">//然后再按照此方法对这两部分数据分别进行快速排序，</span> <span class="token comment">//整个过程可以递归进行，直到整个数据变成有序序列。</span> <span class="token keyword">func</span> <span class="token function">quickSort</span><span class="token punctuation">(</span>arr <span class="token punctuation">[</span><span class="token punctuation">]</span><span class="token builtin">int</span><span class="token punctuation">,</span> start<span class="token punctuation">,</span> end <span class="token builtin">int</span><span class="token punctuation">)</span> <span class="token punctuation">{</span> <span class="token keyword">if</span> start <span class="token operator"><</span> end <span class="token punctuation">{</span> i<span class="token punctuation">,</span> j <span class="token operator">:=</span> start<span class="token punctuation">,</span> end key <span class="token operator">:=</span> arr<span class="token punctuation">[</span><span class="token punctuation">(</span>start<span class="token operator"> </span>end<span class="token punctuation">)</span><span class="token operator">/</span><span class="token number">2</span><span class="token punctuation">]</span> <span class="token comment">//取最中间的一个数当作参考值</span> <span class="token keyword">for</span> i <span class="token operator"><=</span> j <span class="token punctuation">{</span> <span class="token comment">//从i开始向后搜索，找到第一个大于key的arr[i]，将arr[i]和arr[j]交换</span> <span class="token keyword">for</span> arr<span class="token punctuation">[</span>i<span class="token punctuation">]</span> <span class="token operator"><</span> key <span class="token punctuation">{</span> i<span class="token operator"> </span> <span class="token punctuation">}</span> <span class="token comment">//从j开始向前搜索，找到第一个小于key的arr[j]，将arr[j]和arr[i]交换</span> <span class="token keyword">for</span> arr<span class="token punctuation">[</span>j<span class="token punctuation">]</span> <span class="token operator">></span> key <span class="token punctuation">{</span> j<span class="token operator">--</span> <span class="token punctuation">}</span> <span class="token keyword">if</span> i <span class="token operator"><=</span> j <span class="token punctuation">{</span> arr<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">,</span> arr<span class="token punctuation">[</span>j<span class="token punctuation">]</span> <span class="token operator">=</span> arr<span class="token punctuation">[</span>j<span class="token punctuation">]</span><span class="token punctuation">,</span> arr<span class="token punctuation">[</span>i<span class="token punctuation">]</span> i<span class="token operator"> </span> j<span class="token operator">--</span> <span class="token punctuation">}</span> <span class="token punctuation">}</span> <span class="token keyword">if</span> start <span class="token operator"><</span> j <span class="token punctuation">{</span> <span class="token function">quickSort</span><span class="token punctuation">(</span>arr<span class="token punctuation">,</span> start<span class="token punctuation">,</span> j<span class="token punctuation">)</span> <span class="token punctuation">}</span> <span class="token keyword">if</span> end <span class="token operator">></span> i <span class="token punctuation">{</span> <span class="token function">quickSort</span><span class="token punctuation">(</span>arr<span class="token punctuation">,</span> i<span class="token punctuation">,</span> end<span class="token punctuation">)</span> <span class="token punctuation">}</span> <span class="token punctuation">}</span> <span class="token punctuation">}</span> <span class="token keyword">func</span> <span class="token function">main</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token punctuation">{</span> arr <span class="token operator">:=</span> <span class="token punctuation">[</span><span class="token punctuation">]</span><span class="token builtin">int</span><span class="token punctuation">{</span><span class="token number">3</span><span class="token punctuation">,</span> <span class="token number">7</span><span class="token punctuation">,</span> <span class="token number">9</span><span class="token punctuation">,</span> <span class="token number">8</span><span class="token punctuation">,</span> <span class="token number">38</span><span class="token punctuation">,</span> <span class="token number">93</span><span class="token punctuation">,</span> <span class="token number">12</span><span class="token punctuation">,</span> <span class="token number">222</span><span class="token punctuation">,</span> <span class="token number">45</span><span class="token punctuation">,</span> <span class="token number">93</span><span class="token punctuation">,</span> <span class="token number">23</span><span class="token punctuation">,</span> <span class="token number">84</span><span class="token punctuation">,</span> <span class="token number">65</span><span class="token punctuation">,</span> <span class="token number">2</span><span class="token punctuation">}</span> <span class="token function">quickSort</span><span class="token punctuation">(</span>arr<span class="token punctuation">,</span> <span class="token number">0</span><span class="token punctuation">,</span> <span class="token function">len</span><span class="token punctuation">(</span>arr<span class="token punctuation">)</span><span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">)</span> fmt<span class="token punctuation">.</span><span class="token function">Println</span><span class="token punctuation">(</span>arr<span class="token punctuation">)</span> <span class="token punctuation">}</span> </code></pre>

Output：

<pre><code>[2 3 7 8 9 12 23 38 45 65 84 93 93 222] </code></pre> 到此这篇关于“golang_算法:快速排序算法”的文章就介绍到这了,更多文章或继续浏览下面的相关文章，希望大家以后多多支持JQ教程网！

您可能感兴趣的文章：
javascript排序算法代码解析
php排序算法 PHP版快速排序与冒泡排序
php 实现冒泡排序的简单例子
javascript常见排序算法实现代码
JS随机快速排序的代码分享
php有必要学算法吗
php冒泡排序与快速排序的例子
php快速排序三种方法
java排序算法
php实用快速排序算法的实例代码