java 版数据结构与算法
【摘要】
学习目标 衡量一个算法是否好坏的标准 各种常用查找算法、排序算法的掌握 递归的原理及实现 递归的各种应用 快速排序算法的实现 算法(algorithm)：对一个现有的问题我们采取的解决过程及方法，可简单可复杂，可高效可低效。一个用算法实现的程序会耗费两种资源：处理时间和内存。很显然，一个好的算法应该是耗费时间少、所用内存低...
-
-
-
学习目标
-
衡量一个算法是否好坏的标准
-
各种常用查找算法、排序算法的掌握
-
递归的原理及实现
-
递归的各种应用
-
快速排序算法的实现
-
-
算法(algorithm)：
-
对一个现有的问题我们采取的解决过程及方法，可简单可复杂，可高效可低效。一个用算法实现的程序会耗费两种资源：处理时间和内存。很显然，一个好的算法应该是耗费时间少、所用内存低，但是，在实际中，我们往往不能两方面顾全!
-
算法的效率分析标准：
-
衡量算法是否高效主要是从以下几个方面来分析：
-
• 简单性和清晰度
-
一般我们都希望算法越简单越清晰就越好，但是要保证效率为前提。可是，往往我们在复杂的项目开发中所遇见的问题比较复杂，对时间和空间效率的要求也较高，因此，算法一般都会比较复杂。
-
• 空间效率
-
注意：这里的空间效率并不是指算法代码占用的内存指令空间,而是指代码中的数据分配(变量与变量所引用值的分配)以及方法调用所使用的内存(调用栈的空间分配)。比如，我们常用的递归，虽然会使代码清晰简单，但是内存的使用也会大大提高。理想的，程序所使用的内存应该和数据及方法调用 所占用内存相等。但事实总是会有些额外的开销！因此，空间效率也是我们衡量算法的方面之一。
-
• 时间效率
-
针对同一任务所使用的不同算法所执行的时间都会不同。
-
比如：在一个数据集合中查找数据，我们会从第一个数据开始查找，一直找到需要的数据为止，如果查找数据存在，则这种查找方式(称之为线性查找)一般要查找半个列表！然而，如果数据的排放是有序的，则通过另一种查找方法会更有效，即二分查找法，首先从集合的中间开始，如果查找值在中间值的前面，则从集合的前一半重复查找，否则从后一半查找，每执行一次则将查找的集合减少为前一次的一半。
-
算法的类型：
-
所有的算法可以大概分为以下三种类型：
-
1．贪婪算法(greedy algorithm)
-
该算法每一步所做的都是当前最紧急、最有利或者最满意的，不会考虑所做的后果，直到完成任务。这种算法的稳定性很差，很容易带来严重后果，但是，如果方向正确，那该算法也是高效的。
-
2．分治算法(divide-and-conquer algorithm)
-
该算法就是将一个大问题分解成许多小问题，然后单独处理这些小问题，最终将结果结合起来形成对整个问题的解决方案。当子问题和总问题类型类似时，该算法很有效，递归就属于该算法。
-
3．回溯算法(backtracking algorithm)
-
也可以称之排除算法，一种组织好的试错法。某一点，如果有多个选择，则任意选择一个，如果不能解决问题则退回选择另一个，直到找到正确的选择。这种算法的效率很低，除非运气好。比如迷宫就可以使用这种算法来实现。
-
实际上，我们对算法的效率高低评价，主要是在时间和内存之间权衡。根据实际情况来决定，比如有的客户不在乎耗用的内存是多少，他在乎的是执行的速度，那么一个用内存来换取更高执行时间的算法可能是更好的。同样，有的客户可能不想耗用过多内存同时对速度也不是特别要求。不管怎样，效率是算法的主要特性，因此关注算法的性能尤其重要！标准的测量方法就是找出一个函数(增长率)，将执行时间表示为输入大小的函数。选择处理的输入大小来说增长率比较低的算法！
-
计算增长率的方式：
-
1．测量执行时间
-
通过System.currentTimeMillis()方法来测试
-
部分代码:
-
// 测量执行时间
-
static void calculate_time()
-
{
-
long test_data = 1000000;
-
long start_time = 0;
-
long end_time = 0;
-
int testVar = 0;
-
-
-
for (int i = 1; i <= 5; i++)
-
{
-
// 算法执行前的当前时间
-
start_time = System.currentTimeMillis();
-
for(int j = 1; j <= test_data; j++)
-
{
-
testVar++;
-
testVar--;
-
}
-
// 算法执行后的当前时间
-
end_time = System.currentTimeMillis();
-
// 打印总共执行时间
-
System.out.println("test_data = " + test_data + "\n" +
-
"Time in msec = " + (end_time - start_time) + "ms");
-
环后将循环次数加倍
-
test_data = test_data * 2;
-
}
-
}
-
以上代码将分别计算出1000000、2000000、4000000...次的循环时间。
-
缺点：
-
不同的平台执行的时间不同
-
有些算法随着输入数据的加大，测试时间会变得不切实际！
-
2．指令计数
-
指令---指编写算法的代码.对一个算法的实现代码计算执行指令次数。两种类型指令：不管输入大小，执行次数永远不变；执行次数随着输入大小改变而改变。一般，我们主要测试后一种指令。
-
例：计算指令执行次数
-
static void calculate_instruction()
-
{
-
long test_data = 1000;
-
int work = 0;
-
-
for (int i = 1; i <= 5; i++)
-
{
-
int count = 0;
-
for (int k = 1; k <= test_data; k++)
-
{
-
for(int j = 1; j <= test_data; j++)
-
{
-
// 指令执行次数计数
-
count++;
-
work++;
-
work--;
-
}
-
}
-
-
System.out.println("test_data = " + test_data + "\n" +
-
"Instr. count = " + count );
-
-
test_data = test_data * 2;
-
}
-
}
-
3．代数计算
-
代码1：
-
long end_time = 0; t1
-
int testVar = 0; t2
-
for (int i = 1; i <= test_data; i++) t3
-
{
-
testVar++; t4
-
testVar--; t4
-
}
-
假设t1 --- t4分别代表每条语句的执行时间，那么，以上代码的总执行时间为：t1 + t2 + n(t3 + 2t4).其中n = test_data,当test_data增大时，t1和t2可以忽略不计，也就是说，对于很大的n,执行时间可以近似于：n(t3 + 2t4)
-
4．测量内存使用率
-
一个算法中包含的对象和引用的数目，越多则内存使用越高，反之越低。
-
比较增长率：
-
1.代数比较法
-
条件1：c≦ f(n)/g(n) ≦ d (其中c和d为正常数，n代表输入大小)
-
当满足以上条件1时，则f(n)和g(n)具备相同的增长率，或者两函数复杂度的阶相同！
-
如：f(n) = n + 100 和 g(n) = 0.1n + 10两函数就具备相同的增长率。
-
条件2： 当n增大时，f(n)/g(n)趋向于0
-
当满足此条件2时，则该两个增长函数有不同的增长率。
-
比如：f(n) = 10000n + 20000 和 g(n) = n?2 + n + 1 。请大家比较以上两函数增长率是否一样，如果不一样，谁的增长率小？
-
2．大O表示法
-
如果f的增长率小于或者等于g的增长率，则我们可以用如下的大O表示法：
-
f = O(g)
-
O表示on the order of
-
将代码1的代数增长率函数用大O表达式如下：
-
f(n) = t1 + t2 + n(t3 + 2t4)
-
= a1*n + a
-
= O(n)
-
其中a1 = t3 + 2t4; a = t1 + t2
-
3．最佳、最差、平均性能
-
对每一个算法不能只考虑单一的增长率，而应该给出最佳、最差、平均的增长率函数
-
-
查找算法：
-
1．线性查找
-
从数组的第一个元素开始查找，并将其与查找值比较，如果相等则停止，否则继续下一个元素查找，直到找到匹配值。
-
注意：要求被查找的数组中的元素是无序的、随机的。
-
比如，对一个整型数组的线性查找代码：
-
static boolean linearSearch(int target, int[] array)
-
{
-
// 遍历整个数组，并分别将每个遍历元素与查找值对比
-
for (int i = 0; i < array.length; i++)
-
{
-
if (array[i] == target)
-
{
-
return true;
-
}
-
}
-
-
return false;
-
}
-
分析该算法的三种情况：
-
a.最佳情况
-
要查找的值在数组的第一个位置。也就是说只需比较一次就可达到目的，因此最佳情况的大O表达式为：O(1)
-
b.最差情况
-
要查找的值在数组的末尾或者不存在，则对大小为n的数组必须比较n次，大O表达式为：O(n)
-
c.平均情况
-
估计会执行：(n + (n - 1) + (n - 2) + ….. + 1)/n = (n + 1) / 2次比较，复杂度为O(n)
-
-
2．二分查找
-
假设被查找数组中的元素是升序排列的，那我们查找值时，首先会直接到数组的中间位置(数组长度/2)，并将中间值和查找值比较，如果相等则返回，否则，如果当前元素值小于查找值，则继续在数组的后面一半查找(重复上面过程)；如果当前元素值大于查找值，则继续在数组的前面一半查找，直到找到目标值或者无法再二分数组时停止。
-
注意：二分查找只是针对有序排列的各种数组或集合
-
代码：
-
static boolean binarySearch(int target, int[] array)
-
{
-
int front = 0;
-
int tail = array.length - 1;
-
-
// 判断子数组是否能再次二分
-
while (front <= tail)
-
{
-
// 获取子数组的中间位置，并依据此中间位置进行二分
-
int middle = (front + tail) / 2;
-
-
if (array[middle] == target)
-
{
-
return true;
-
}
-
else if (array[middle] > target)
-
{
-
tail = middle - 1;
-
}
-
else
-
{
-
front = middle + 1;
-
}
-
}
-
-
return false;
-
}
-
最佳情况：
-
中间值为查找值，只需比较一次，复杂度为O(1)
-
最差、平均：
-
当我们对一个数组执行二分查找时，最多的查找次数是满足n < 2^k的最小整数k，比如：当数组长度为20时，那么使用二分法的查找次数最多为5次，即：2^5 > 20因此可以得出二分法的最差及平均情况的复杂度为O(logn)。
-
分析：1，2，3，4，5，6，7，8，9
-
在上面数组中查找7需要比较多少次？
-
查找2.5需要比较多少次？(假设存储的数值都是双精度数据类型)
-
显然，对于一个有序数组或集合，使用二分查找会比线性查找更加有效！但是注意，虽然二分法效率更高，但使用的同时系统也会增加额外的开销，为什么？
-
-
-
排序算法：
-
1．选择排序
-
首先在数组中查找最小值，如果该值不在第一个位置，那么将其和处在第一个位置的元素交换，然后从第二个位置重复此过程，将剩下元素中最小值交换到第二个位置。当到最后一位时，数组排序结束。
-
代码：
-
static void selectionSort(int[] array)
-
{
-
for (int i = 0; i < array.length - 1; i++)
-
{
-
int min_idx = i;
-
-
for (int j = i + 1; j < array.length; j++)
-
{
-
if (array[j] < array[min_idx])
-
{
-
min_idx = j;
-
}
-
}
-
-
if (min_idx != i)
-
{
-
swap(array,min_idx,i);
-
}
-
-
}
-
}
-
从上面代码我们可以看出，假设数组大小为n，外循环共执行n-1次；那么第一次执行外循环时，内循环将执行n-1次；第二次执行外循环时内循环将执行n-2次；最后一次执行外循环时内循环将执行1次，因此我们可以通过代数计算方法得出增长函数为：(n - 1) + (n - 2) + (n - 3) + ….. + 1 = n(n - 1) / 2 = 1/2 * n^2 + 1/2 * n，即可得出复杂度为：O(n^2)。我们可以分析得知，当数组非常大时，用于元素交换的开销也相当大。这都属于额外开销，是呈线性增长的。注意：如果是对存储对象的集合进行排序，则存储对象必须实现Comparable接口，并通过compareTo()方法来比较大小。
-
-
2．冒泡排序
-
冒泡排序法是运用数据值比较后，依判断规则对数据位置进行交换，以达到排序的目的。具体算法是将相邻的两个数据加以比较，若左边的值大于右边的值，则将此两个值互相交换；若左边的值小于等于右边的值，则此两个值的位置不变。右边的值继续和下一个值做比较，重复此操作，直到比较到最后一个值。此方法在每比较一趟就会以交换位置的方式将该趟的最大者移向数组的尾端，就像气泡从水底浮向水面一样，到水面时气泡最大，故称为冒泡排序法。
-
冒泡和选择的复杂度很相似，对于大小为n的数组，对于最佳、最差还是平均，冒泡的复杂度都是O(n^2)。注意：冒泡的最差情况是高于线性的
-
大家可以发现，冒泡的效率是比较低的，因为它不论是那种情况复杂度都是O(n^2)，但是我们可以改进一下，来实现当冒泡处于最佳情况时只会执行一次外循环，即实现线性。我们可以推断，如果执行一次外循环，结果并没有发生元素交换(调用swap()),那么我们就能判定该数组是已经排序好的，而通过上面的冒泡程序得知，不管是否已经排序，外循环会执行n-1次，而最佳情况就是发生在第一次外循环，因此，我们可以改良以上程序，通过使用一个布尔型的值来记录是否有元素交换的状态，是就为true，否就为false，如果内循环没有交换元素(没有改变布尔值)，那么直接返回。
-
改后代码：
-
public void bubbleSort(int[] array)// 冒泡排序算法
-
{
-
int out, in;
-
// 外循环记录冒泡次数
-
for (out = nElems - 1; out > 1; out--)
-
{
-
boolean flag = false;
-
// 进行冒泡
-
for (in = 0; in < out; in++)
-
{
-
// 交换数据
-
if (array[in] > array[in + 1]) {
-
swap(in, in + 1);
-
flag=true;
-
}
-
}
-
if(!flag){break;}
-
-
}
-
} // end bubbleSort()
-
-
private void swap(int one, int two)// 交换数据
-
{
-
int temp = array[one];
-
array[one] = array[two];
-
array[two] = temp;
-
}
-
注意：以上改良程序只会提高最佳情况的性能，而对于平均和最差来说，复杂度还是O(n^2)。该改良程序适合于对已经排序好的数组或者只需稍微重排的数组，比选择排序性能更好。
-
-
3．插入排序
-
插入排序是对于欲排序的元素以插入的方式寻找该元素的适当位置，以达到排序的目的。插入排序法的优点是利用一个一个元素的插入比较，将元素放入适当的位置，所以是一种很简单排序方式。但因每次元素插入都必须与之前已排序好的元素做比较，故需花费较长的排序时间。
-
步骤如下：(假设数组长度为n)
-
a.对数组的每次(第i次)循环，下标值为i的元素应该插入到数组的前i个元素的正确位置(如果是升序，则i元素应插入到小于它的元素之后，大于它的元素之前，降序则反之)
-
b.每次循环(第i次)结束时，应保证前i个元素排序是正确的！
-
c.包含两个循环，外循环(循环变量为i)遍历下标从1到n-1的元素，保存每次循环的所遍历的元素的值，内循环(循环变量为k)从i -1开始，即遍历前将k赋值为i-1，每次k--，直到k < 0。在内循环中，将第i个元素和该元素之前的所有元素一一对比，并将元素插入到合适的位置，如果第i个元素的位置是正确的，那么就跳出内循环，重新开始外循环。
-
代码：
-
public void insertSort()// 插入排序算法
-
{
-
int in, out;
-
for (out = 1; out < nElems; out++)// 外循环是给每个数据循环
-
{
-
int temp = array[out]; // 先取出来保存到临时变量里
-
in = out; // in是记录插入数据之前的每个数据下标
-
// while内循环是找插入数据的位置，并且把该位置之后的数据（包括该位置）
-
// 依次往后顺移。
-
while (in > 0 && array[in - 1] >= temp) {
-
array[in] = array[in - 1]; // 往后顺移
-
--in; // 继续往前搜索
-
}
-
array[in] = temp; // 该数据要插入的位置
-
} // end for
-
} // end insertionSort()
-
分析：内循环在第一次外循环时执行1次，第二次外循环时执行2次，。。。。第n - 1次外循环时执行n - 1次，因此，插入排序的最差和平均情况的性能是O(n^2)。但是，在最佳情况下(即数组中的元素顺序是完全正确的)，插入排序的性能是线性的。注意：插入排序适合针对于已排序元素多的数组，即数组中已排序的元素越多，插入排序的性能就越好。
-
-
-
递归(recursive)：
-
定义函数1：sum(1) = 1
-
定义函数2：sum(n) = n + sum(n - 1)
-
假设n = 5，那么sum(5) = 5 + sum(4)
-
=5 + 4 + sum(3)
-
=5 + 4 + 3 + sum(2)
-
=5 + 4 + 3 + 2 + sum(1)
-
=5 + 4 + 3 + 2 + 1
-
以上这种在自身中使用自身定义函数的过程称之递归。
-
阶乘递归(factorial recursive)：
-
阶乘!4 = 4 * 3 * 2 * 1
-
可以用递归来表示为：
-
factorial(1) = 1
-
factorial(n) = n * factorial(n - 1)
-
其中n>1。
-
斐波纳契递归(fibonacci recursive)
-
1,1,2,3,5,8,13,21,34,55,89,144…………
-
斐波纳契数列的第一个和第二个数字都定义为1，后面的每个数字都为前两个数之和。
-
用递归表示为：
-
fibonacci(1) = fibonacci(2) = 1
-
fibonacci(n) = fibonacci(n-1) + fibonacci(n-2)
-
其中n>2。
-
实现递归必须满足两个条件：
-
1．基本条件(base case)的成立
-
实际上就是定义递归应该什么时候终止，比如在上面两个例子中，factorial(1) = 1和fibonacci(1) = fibonacci(2) = 1就是递归的基本条件，一旦当递归执行到满足基本条件时就是结束递归。
-
2．递归步骤
-
对于所有的n值，函数都是以其自身通过n值较小的函数来定义，也就是说，所有n值函数通过许多步骤来达到最终用n值较小的函数(基本条件)来定义。可以得知，递归函数就是反复执行递归步，直到n达到基本条件为止。
-
factorial的递归代码实现：
-
factorial：
-
static int factorial(int n)
-
{
-
// 基本条件
-
1 if (n <= 1)
-
{
-
2 return 1;
-
}
-
else
-
{
-
// 递归步，执行n-1次
-
3 return n * factorial(n - 1);
-
}
-
}
-
分析：
-
语句3将被执行n-1次，一直到n<=1时结束递归。
-
假设n=4，那么我们可以得知:
-
第一步：调用factorial(4)
-
第二步：调用4 * factorial(3) n = 4
-
第三步：调用3* factorial(2) n = 3
-
第四步：调用2 * factorial(1) n = 2
-
第五步：返回1给factorial(2)
-
第六步：返回2给factorial(3)
-
第七步：返回6给factorial(4)
-
第八步：返回值24。
-
-
fibonacci：
-
static int fibonacci(int n)
-
{
-
// 基本条件
-
if (n <= 2)
-
{
-
return 1;
-
}
-
else
-
{
-
// 递归步，执行n-2次
-
return fibonacci(n-1) + fibonacci(n-2);
-
}
-
}
-
分析：可以用递归调用树来描述。每次都会两次调用到自己。
-
编写递归应注意事项：
-
----避免死循环，一般都是由于没有基本条件而造成，也可能是递归步的逻辑错误导致。
-
递归方法的运行实现原理：
-
我们发现，递归就是一个不停调用方法自身的一个过程，即方法的反复调用！
-
计算机是通过栈的机制来实现方法调用的。首先，我们来了解下计算机的方法调用机制：
-
1．程序执行前，计算机会在内存中创建一个调用栈 ，一般会比较大
-
2．当调用某个方法时，会有一个和该被调用方法相关的记录信息被推入到栈中
-
3．被推入到栈中的记录信息包括内容：传递到被调用方法中的参数值、该方法的局部变量、该方法的返回值。
-
4．当返回某个方法或者方法结束时，会从栈中取出对应的方法记录信息
-
栈的使用机制：后进先出(LIFO)。注意：最然递归方法简洁，但是效率不是完全就比迭代高，有时甚至低。因为我们考虑算法不仅要从时间、增长率来考虑，还要考虑空间(一般指内存)问题，递归的栈空间是我们必须考虑的，因为每次方法的调用都需额外的空间来存储相关信息。
-
递归和查找：
-
在前面，我们已使用迭代来实现了线性和二分查找，同样，这两种算法也能用递归来实现，但是线性查找用递归来实现并没任何优势，因此一般线性不采用递归。
-
线性查找的递归实现：
-
static boolean linearSearch(int[] array, int target, int pos)
-
{
-
if (pos >= array.length)
-
{
-
return false;
-
}
-
else if (array[pos] == target)
-
{
-
return true;
-
}
-
else
-
{
-
return linearSearch(array,target,pos + 1);
-
}
-
}
-
注意：pos = 0
-
二分查找的递归实现：
-
static boolean binarySearch(int[] array, int target, int front, int tail)
-
{
-
if (front > tail)
-
{
-
return false;
-
}
-
else
-
{
-
int middle = (front + tail) / 2;
-
if (array[middle] == target)
-
{
-
return true;
-
}
-
else if (array[middle] < target)
-
{
-
return binarySearch(array,target,middle + 1,tail);
-
}
-
else
-
{
-
return binarySearch(array,target,front,middle - 1);
-
}
-
}
-
}
-
二分查找的递归方法在平均和最差情况下的复杂度和用迭代实现二分的一样，都是O(logn)。其空间复杂度也为O(nlogn)。所以，用递归实现的二分查找也是可行的。
-
-
递归和迭代的选择：
-
在我们选择一个算法来实现一个方法时，我们应该对多个理由进行对比，高效+简洁+易维护就是最好的。一般，递归由于方法调用的时间和空间的开销，往往比相应的非递归方法效率低，但有时递归的精确和简洁有时称为用户首选。
-
尾递归：
-
递归调用之后算法不用再做任何工作，那这个算法就是尾递归。尾递归的主要特点就是编译器可将尾递归代码转换成机器语言形式的循环，从而不会产生与递归有关的开销。
-
例：阶乘的尾递归实现
-
static int factIter(int n, int result)
-
{
-
if (n <= 1)
-
{
-
return result;
-
}
-
else
-
{
-
return factIter(n-1, n*result);
-
}
-
}
-
递归和排序：
-
前面的几种排序的复杂度都是O(n^2)，效率不高，这里我们要学习两种通过分治算法(递归)来实现的比较高效的排序方法，分别是快速排序和归并排序(扩展内容)。注意：效率越高其算法的编写复杂性自然也会提高
-
快速排序：
-
快速排序的思想其实就是，先找个参照物（一般以最后一个数据作为参照物）然后用两个变量遍历该数据，左变量从左边找第一个比参照物大的数据，右变量从右边开始找第一个比参照物小的数据，然后交换这两个数据。然后左变量继续往右边找一个比参照物大的数据，右变量继续往左找比参照物小的数据，然后再交换这两个数据。依次直到左变量和右变量出现交差为止。然后把左变量所指的值和参照物进行交换。交换完之后，从左变量的位置开始分成两半，然后先从前半部分按照上面的方法进行排序，排完后在从后半部分进行同样的排序，直到排完为止，整个思想就是个递归调用！
-
-
原理：
-
1．首先，寻找数组的中间值，然后将该中间值看成一个枢轴(pivot)
-
2．接着开始划分数据，将所有小于枢轴的数据项都排放在它的位置之前，所有大于枢轴的数据项都排放在它的位置之后。枢轴(中间值)最终所在位置是由其自身的实际值大小来决定的，如果它是数组最大值，那么它就处于数组的最右侧，否则处于最左侧。
-
3．上面的划分过程递归应用于所有的根据枢轴划分出的子数组中。每一个子数组必须拥有自己的枢轴。每个子数组由枢轴左、右的数据元素组成。
-
4．当子数组小到不能在划分的时候(比如数组元素个数小于2)，快速排序结束。
-
分析：通过以上原理可以理解，快速排序是基于二分法的基础上实现的一个复杂而又高效的排序算法，在排序算法中，最为关键的步骤就是枢轴的位置控制、数组的划分。如果我们把划分的原理理解了，那也就基本掌握了快速排序算法。下面我们来重点分析一下划分是怎样实现的：
-
划分：
-
第一步：将枢轴与子数组中的最后一个数据项交换。
-
第二步：建立一个边界(boundary),最初该边界在数组的第一个元素之前。该边界主要是用于区分大于枢轴的数据元素和小于枢轴的数据元素。
-
第三步：从划分出的子数组的第一个元素开始，逐步扫描整个数组，在扫描过程中，如果遇见小于枢轴的元素，那么就将该元素与边界后的第一个元素交换，同时边界得往前移动一个位置。
-
第四步：当扫描完整个数组之后，得将枢轴与边界后的第一个元素交换，这时，划分过程完成了。
-
代码如下：
-
static int partition(int[] array, int front, int tail)
-
{
-
// 用于保存中间位置
-
int middle;
-
// 保存边界位置
-
int boundary;
-
// 保存枢轴位置
-
int pivot;
-
// 保存临时值，用于值交换
-
int temp;
-
-
// 获取中间值的位置
-
middle = (front + tail) / 2;
-
// 得到枢轴
-
pivot = array[middle];
-
-
// 执行第一步，将枢轴与子数组中的最后一个数据项交换
-
array[middle] = array[tail];
-
array[tail] = pivot;
-
-
// 执行第二步，建立一个边界(boundary),最初该边界在数组的第一个元素之前
-
boundary = front;
-
-
// 执行第三步，遍历子数组，并将每个元素和枢轴对比，并改变元素位置
-
for (int i = front; i < tail; i++)
-
{
-
// 如果当前元素小于枢轴，则将该元素和边界互换，并将交换后的边界往后移一位
-
if (array[i] < pivot)
-
{
-
temp = array[boundary];
-
array[boundary] = array[i];
-
array[i] = temp;
-
-
boundary++;
-
}
-
}
-
-
// 执行第四步，将枢轴与边界后的第一个元素交换
-
temp = array[tail];
-
array[tail] = array[boundary];
-
array[boundary] = temp;
-
-
// 返回边界位置
-
return boundary;
-
}
-
-
快速排序实现如下：
-
static void quickSort(int[] array, int front, int tail)
-
{
-
if (front < tail)
-
{
-
int pivotPosition = partition(array,front,tail);
-
// 递归实现子数组的划分，每次根据不同边界来划分
-
// 划分枢轴的左数组
-
quickSort(array,front,pivotPosition - 1);
-
// 划分枢轴的右数组
-
quickSort(array,pivotPosition + 1,tail);
-
}
-
}
-
注意：快速排序在最好情况下(每个枢轴在它的子数组的中间划分之后就会终止，即枢轴为每个子数组的中值)的最大运行时间是O(nlogn),最差情况下(在每个阶段，枢轴恰好是它的子数组的最小数据项-升序)的运行时间是O(n^2)，幸好，快速排序的平均情况下的时间是O(nlogn)；快速排序的空间需求在平均情况下是O(nlogn)，最坏情况下是O(n)。因此，快速排序比插入、选择、冒泡排序的效率都要高，但是，在n值较小的情况下，其它排序方法会比快速更快。高效的排序法应该是结合快速排序和其它排序来实现数组排序。当数组很大时，我们先采用快速排序，但一旦划分出子数组变得很小时(这时数组元素已大部分被排序)，我们应该停止递归快速排序，而采用另一种非递归排序算法。
-
-
内容总结
-
算法的效率分析标准从三方面：简单清晰、空间、时间。
-
算法增长率的计算：时间、指令执行次数、代数计算
-
每种算法的三种情况分析，最佳、平均、最差。
-
代数表述法与大O表示法
-
查找算法：线性查找、二分查找，排序算法:插入排序、选择排序、冒泡排序、快速排序等。
-
递归的方法调用栈原理
-
尾递归的优化
-
-
-
独立实践
-
1， 实现对员工数据的二分查找、排序(普通排序算法和高级算法各用一种)。
-
2， 编写递归实现Fibonacci和Factorial
文章来源: aaaedu.blog.csdn.net，作者：tea_year，版权归原作者所有，如需转载，请联系作者。
原文链接：aaaedu.blog.csdn.net/article/details/52738124
【版权声明】本文为华为云社区用户转载文章，如果您发现本社区中有涉嫌抄袭的内容，欢迎发送邮件进行举报，并提供相关证据，一经查实，本社区将立刻删除涉嫌侵权内容，举报邮箱：
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论（0）