冒泡排序
因为在归并排序的简化过程中需要用到冒泡排序,所以这里先做一下简单介绍。
冒泡排序(Bubble Sort),是一种计算机科学领域的较简单的排序算法。
它重复地走访过要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成。
这个算法的名字由来是因为越大的元素会经由交换慢慢“浮”到数列的顶端,故名。
算法原理
- 比较相邻的元素。如果第一个比第二个大,就交换他们两个。
- 对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对。在这一点,最后的元素应该会是最大的数。
- 针对所有的元素重复以上的步骤,除了最后一个。
- 持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较。
时间复杂度
冒泡排序的最优时间复杂度为:\(O(n)\)
最坏时间复杂度为:\(O(n^2)\)
平均时间复杂度为:\(O(n^2)\)
示例代码
public static void BubbleSort(Integer[] list) {
for (int i = 0; i < list.length; i++) {
for (int j = i + 1; j < list.length; j++) {
if (list[i] > list[j]) {
swap(list, i, j);
}
}
}
}
在归并排序中用到的是冒泡排序的修改版,多了两个参数first和last,只对数组中索引从first到last的元素进行冒泡排序,示例代码如下。
public static void BubbleSort(
Integer[] list,
int first,
int last) {
for (int i = first; i <= last; i++) {
for (int j = i + 1; j <= last; j++) {
if (list[i] > list[j]) {
swap(list, i, j);
}
}
}
}
归并排序
归并排序(MERGE-SORT)是建立在归并操作上的一种有效的排序算法,该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为二路归并。
算法原理
归并操作的工作原理如下:
- 第一步:申请空间,使其大小为两个已经排序序列之和,该空间用来存放合并后的序列
- 第二步:设定两个指针,最初位置分别为两个已经排序序列的起始位置
- 第三步:比较两个指针所指向的元素,选择相对小的元素放入到合并空间,并移动指针到下一位置
- 重复步骤3直到某一指针超出序列尾
- 将另一序列剩下的所有元素直接复制到合并序列尾
时间复杂度
时间复杂度为\(O(nlog₂n)\) 这是该算法中最好、最坏和平均的时间性能。
空间复杂度为 \(O(n)\)
比较操作的次数介于\((nlogn) / 2\)和\(nlogn – n + 1\)。
赋值操作的次数是\((2nlogn)\)。
归并算法的空间复杂度为:\(O (n)\)
归并排序比较占用内存,但却是一种效率高且稳定的算法。
示例代码
public static void MergeArray(
Integer[] list,
int first,
int mid,
int last) {
int i = first;
int j = mid + 1;
int m = mid;
int n = last;
ArrayList<Integer> tmp = new ArrayList<>(
last - first + 1);
while (i <= m && j <= n) {
if (list[i] <= list[j]) {
tmp.add(list[i++]);
} else {
tmp.add(list[j++]);
}
}
while (i <= m) {
tmp.add(list[i++]);
}
while (j <= n) {
tmp.add(list[j++]);
}
for (int index = 0; index < tmp.size(); index++) {
list[first + index] = tmp.get(index);
}
}
public static void MergeSort(
Integer[] list,
int first,
int last) {
if (first < last) {
int mid = (first + last) / 2;
MergeSort(list, first, mid);
MergeSort(list, mid + 1, last);
MergeArray(list, first, mid, last);
}
}
归并排序升级版
下图是对1到100个随机数字进行排序,冒泡排序和归并排序运行的时间比较。(单位:秒)
可以看出,虽然归并排序的运行时间小于冒泡排序,但是在排序数字数目较少时(20个以下),冒泡排序的性能要优于归并排序,由此得出以下归并排序的升级版:
设置一个阈值min,当需要排序的数字数目大于min时,继续归并排序;反之,当需要排序的数字数目小于min时,进行冒泡排序。
示例代码如下,这里设置min为需要传入的参数。
public static void MergeSort2(
Integer[] list,
int first,
int last,
int min) {
if (last - first > min) {
int mid = (first + last) / 2;
MergeSort(list, first, mid);
MergeSort(list, mid + 1, last);
MergeArray(list, first, mid, last);
} else {
BubbleSort(list, first, last);
}
}
下面分别对传入参数min为3,4,5,6时对1到100000个随机数字进行排序的运行时间比较。(单位:秒)
放大图像的右下部分。
由于随机数字不稳定的原因,min的不同取值造成的运行时间影响也有所不同。这里的升级版本采取稳定性较好的min=5,示例代码如下。
public static void MergeSort3(
Integer[] list,
int first,
int last) {
if (last - first > 5) {
int mid = (first + last) / 2;
MergeSort(list, first, mid);
MergeSort(list, mid + 1, last);
MergeArray(list, first, mid, last);
} else {
BubbleSort(list, first, last);
}
}
归并排序并发实现
对于归并排序考虑到以下问题:
既然把一个排序问题递归地分解成两个更小的排序问题,那么可不可以将这两个排序分别在不同线程中进行呢,答案当然是可以的。
下面使用两种方式进行实现,分别使用Callable/Future和Fork/Join框架,在两个线程中分别进行二路分解,当两个线程都分解完成时,再启用归并程序。(这里都采用上面得到的最优归并排序策略MergeSort3)
Callable/Future实现示例代码如下。
public static class MergeSort4 implements Callable<Boolean> {
private ExecutorService threadPool;
private Future<Boolean> loadResult0;
private Future<Boolean> loadResult1;
private Integer[] list;
private int first;
private int last;
public MergeSort4(Integer[] list, ExecutorService threadPool) {
this.list = list;
this.threadPool = threadPool;
first = 0;
last = list.length - 1;
}
public MergeSort4(Integer[] list, int first, int last,
ExecutorService threadPool) {
this.list = list;
this.first = first;
this.last = last;
this.threadPool = threadPool;
}
/**
* Computes a result, or throws an exception if unable to do so.
*
* @return computed result
* @throws Exception if unable to compute a result
*/
@Override
public Boolean call() throws Exception {
if (last - first > 5) {
int mid = (first + last) / 2;
loadResult0 = threadPool.submit(
new MergeSort4(list, first, mid, threadPool)
);
loadResult1 = threadPool.submit(
new MergeSort4(list, mid + 1, last, threadPool)
);
try {
if (loadResult0.get() && loadResult1.get()) {
MergeArray(list, first, mid, last);
}
} catch (InterruptedException e) {
e.printStackTrace();
} catch (ExecutionException e) {
e.printStackTrace();
}
} else {
BubbleSort(list, first, last);
}
return true;
}
}
Fork/Join实现示例代码如下。
public static class MergeSort5 extends RecursiveTask {
private Integer[] list;
private int first;
private int last;
public MergeSort5(Integer[] list) {
this.list = list;
first = 0;
last = list.length - 1;
}
public MergeSort5(Integer[] list, int first, int last) {
this.list = list;
this.first = first;
this.last = last;
}
/**
* The main computation performed by this task.
*
* @return the result of the computation
*/
@Override
protected Object compute() {
if (last - first > 5) {
int mid = (first + last) / 2;
MergeSort5 leftTask = new MergeSort5(list, first, mid);
MergeSort5 rightTask = new MergeSort5(list, mid + 1, last);
leftTask.fork();
rightTask.fork();
leftTask.join();
rightTask.join();
MergeArray(list, first, mid, last);
} else {
BubbleSort(list, first, last);
}
return null;
}
}
Fork/Join框架详解
Fork/Join框架介绍
Fork/Join框架是Java7提供了的一个用于并行执行任务的框架, 是一个把大任务分割成若干个小任务,最终汇总每个小任务结果后得到大任务结果的框架。
我们再通过Fork和Join这两个单词来理解下Fork/Join框架,Fork就是把一个大任务切分为若干子任务并行的执行,Join就是合并这些子任务的执行结果,最后得到这个大任务的结果。比如计算1+2+……+10000,可以分割成10个子任务,每个子任务分别对1000个数进行求和,最终汇总这10个子任务的结果。当然,也可以分成更多更小的任务。
Fork/Join框架设计
第一步分割任务。首先我们需要有一个fork类来把大任务分割成子任务,有可能子任务还是很大,所以还需要不停的分割,直到分割出的子任务足够小。
第二步执行任务并合并结果。分割的子任务分别放在双端队列里,然后几个启动线程分别从双端队列里获取任务执行。子任务执行完的结果都统一放在一个队列里,启动一个线程从队列里拿数据,然后合并这些数据。
Fork/Join使用两个类来完成以上两件事情:
- ForkJoinTask:我们要使用ForkJoin框架,必须首先创建一个ForkJoin任务。它提供在任务中执行fork()和join()操作的机制,通常情况下我们不需要直接继承ForkJoinTask类,而只需要继承它的子类,Fork/Join框架提供了以下两个子类:
- RecursiveAction:用于没有返回结果的任务。
- RecursiveTask:用于有返回结果的任务。
- ForkJoinPool:ForkJoinTask需要通过ForkJoinPool来执行,任务分割出的子任务会添加到当前工作线程所维护的双端队列中,进入队列的头部。当一个工作线程的队列里暂时没有任务时,它会随机从其他工作线程的队列的尾部获取一个任务。
Fork/Join框架使用
让我们通过一个简单的需求来使用下Fork/Join框架,需求是:计算1+2+3+4的结果。
使用Fork/Join框架首先要考虑到的是如何分割任务,如果我们希望每个子任务最多执行两个数的相加,那么我们设置分割的阈值是2,由于是4个数字相加,所以Fork/Join框架会把这个任务fork成两个子任务,子任务一负责计算1+2,子任务二负责计算3+4,然后再join两个子任务的结果。
因为是有结果的任务,所以必须继承RecursiveTask,实现代码如下:
public static class CountTask extends RecursiveTask {
private static final int THRESHOLD = 2;
private int start;
private int end;
public CountTask(int start, int end) {
this.start = start;
this.end = end;
}
/**
* The main computation performed by this task.
*
* @return the result of the computation
*/
@Override
protected Integer compute() {
int sum = 0;
boolean canCompute = (end - start) <= THRESHOLD;
if (canCompute) {
for (int i = start; i <= end; i++) {
sum += i;
}
} else {
int middle = (start + end) / 2;
CountTask leftTask = new CountTask(start, middle);
CountTask rightTask = new CountTask(middle + 1, end);
leftTask.fork();
rightTask.fork();
int leftResult = (int) leftTask.join();
int rightResult = (int) rightTask.join();
sum = leftResult + rightResult;
}
return sum;
}
}
这个类是通用的计算1+2+……+n,每次取两个数相加,当传入参数1和4时,为计算1+2+3+4的结果。
附录1:产生一定数量随机数字的方法
public static Integer[] RandomList(int num) {
ArrayList<Integer> list = new ArrayList<>(num);
for (int i = 0; i < num; i++) {
list.add(i);
}
Collections.shuffle(list);
return list.toArray(new Integer[num]);
}
附录2:交换数组中两个索引的元素的方法
public static void swap(Integer[] list, int index1, int index2) {
int tmp = list[index1];
list[index1] = list[index2];
list[index2] = tmp;
}
附录3:主函数(测试程序)
其中range(delta,maxNum+delta,delta)是测试的数组元素数目的取值集合。
public static void main(String[] args) {
File file = new File("MergeSort.txt");
try {
System.setOut(new PrintStream(file));
} catch (FileNotFoundException e) {
e.printStackTrace();
}
int maxNum = 100000;
int delta = 100;
int listNum = 10000;
long lastTime, curTime, nsPerTime;
Integer[] list;
System.out.println("BubbleSort");
for (listNum = delta; listNum <= maxNum; listNum += delta) {
list = RandomList(listNum);
lastTime = System.nanoTime();
BubbleSort(list);
curTime = System.nanoTime();
nsPerTime = curTime - lastTime;
System.out.print(nsPerTime / 1.0E9 + ",");
}
System.out.println();
System.out.println("MergeSort");
for (listNum = delta; listNum <= maxNum; listNum += delta) {
list = RandomList(listNum);
lastTime = System.nanoTime();
MergeSort(list, 0, list.length - 1);
curTime = System.nanoTime();
nsPerTime = curTime - lastTime;
System.out.print(nsPerTime / 1.0E9 + ",");
}
System.out.println();
System.out.println("MergeSort 3");
for (listNum = delta; listNum <= maxNum; listNum += delta) {
list = RandomList(listNum);
lastTime = System.nanoTime();
MergeSort2(list, 0, list.length - 1, 3);
curTime = System.nanoTime();
nsPerTime = curTime - lastTime;
System.out.print(nsPerTime / 1.0E9 + ",");
}
System.out.println();
System.out.println("MergeSort 4");
for (listNum = delta; listNum <= maxNum; listNum += delta) {
list = RandomList(listNum);
lastTime = System.nanoTime();
MergeSort2(list, 0, list.length - 1, 4);
curTime = System.nanoTime();
nsPerTime = curTime - lastTime;
System.out.print(nsPerTime / 1.0E9 + ",");
}
System.out.println();
System.out.println("MergeSort 5");
for (listNum = delta; listNum <= maxNum; listNum += delta) {
list = RandomList(listNum);
lastTime = System.nanoTime();
MergeSort2(list, 0, list.length - 1, 5);
curTime = System.nanoTime();
nsPerTime = curTime - lastTime;
System.out.print(nsPerTime / 1.0E9 + ",");
}
System.out.println();
System.out.println("MergeSort 6");
for (listNum = delta; listNum <= maxNum; listNum += delta) {
list = RandomList(listNum);
lastTime = System.nanoTime();
MergeSort2(list, 0, list.length - 1, 6);
curTime = System.nanoTime();
nsPerTime = curTime - lastTime;
System.out.print(nsPerTime / 1.0E9 + ",");
}
System.out.println();
System.out.println("MergeSort Callable");
for (listNum = delta; listNum <= maxNum; listNum += delta) {
list = RandomList(listNum);
ExecutorService threadPool = Executors.newCachedThreadPool();
MergeSort4 mergeSort4 = new MergeSort4(list, threadPool);
lastTime = System.nanoTime();
Future<Boolean> result = threadPool.submit(mergeSort4);
try {
result.get();
} catch (InterruptedException e) {
e.printStackTrace();
} catch (ExecutionException e) {
e.printStackTrace();
} finally {
threadPool.shutdown();
}
curTime = System.nanoTime();
nsPerTime = curTime - lastTime;
System.out.print(nsPerTime + ",");
}
System.out.println();
System.out.println("MergeSort RecursiveTask");
for (listNum = delta; listNum <= maxNum; listNum += delta) {
list = RandomList(listNum);
ForkJoinPool forkJoinPool = new ForkJoinPool();
MergeSort5 mergeSort5 = new MergeSort5(list);
lastTime = System.nanoTime();
Future result = forkJoinPool.submit(mergeSort5);
try {
result.get();
} catch (InterruptedException e) {
e.printStackTrace();
} catch (ExecutionException e) {
e.printStackTrace();
} finally {
forkJoinPool.shutdown();
}
curTime = System.nanoTime();
nsPerTime = curTime - lastTime;
System.out.print(nsPerTime + ",");
}
System.out.println();
}
附录4:源代码
import java.io.File;
import java.io.FileNotFoundException;
import java.io.PrintStream;
import java.util.ArrayList;
import java.util.Collections;
import java.util.concurrent.*;
public class MergeSort {
public static void main(String[] args) {
File file = new File("MergeSort.txt");
try {
System.setOut(new PrintStream(file));
} catch (FileNotFoundException e) {
e.printStackTrace();
}
int maxNum = 100000;
int delta = 100;
int listNum = 10000;
long lastTime, curTime, nsPerTime;
Integer[] list;
System.out.println("BubbleSort");
for (listNum = delta; listNum <= maxNum; listNum += delta) {
list = RandomList(listNum);
lastTime = System.nanoTime();
BubbleSort(list);
curTime = System.nanoTime();
nsPerTime = curTime - lastTime;
System.out.print(nsPerTime / 1.0E9 + ",");
}
System.out.println();
System.out.println("MergeSort");
for (listNum = delta; listNum <= maxNum; listNum += delta) {
list = RandomList(listNum);
lastTime = System.nanoTime();
MergeSort(list, 0, list.length - 1);
curTime = System.nanoTime();
nsPerTime = curTime - lastTime;
System.out.print(nsPerTime / 1.0E9 + ",");
}
System.out.println();
System.out.println("MergeSort 3");
for (listNum = delta; listNum <= maxNum; listNum += delta) {
list = RandomList(listNum);
lastTime = System.nanoTime();
MergeSort2(list, 0, list.length - 1, 3);
curTime = System.nanoTime();
nsPerTime = curTime - lastTime;
System.out.print(nsPerTime / 1.0E9 + ",");
}
System.out.println();
System.out.println("MergeSort 4");
for (listNum = delta; listNum <= maxNum; listNum += delta) {
list = RandomList(listNum);
lastTime = System.nanoTime();
MergeSort2(list, 0, list.length - 1, 4);
curTime = System.nanoTime();
nsPerTime = curTime - lastTime;
System.out.print(nsPerTime / 1.0E9 + ",");
}
System.out.println();
System.out.println("MergeSort 5");
for (listNum = delta; listNum <= maxNum; listNum += delta) {
list = RandomList(listNum);
lastTime = System.nanoTime();
MergeSort2(list, 0, list.length - 1, 5);
curTime = System.nanoTime();
nsPerTime = curTime - lastTime;
System.out.print(nsPerTime / 1.0E9 + ",");
}
System.out.println();
System.out.println("MergeSort 6");
for (listNum = delta; listNum <= maxNum; listNum += delta) {
list = RandomList(listNum);
lastTime = System.nanoTime();
MergeSort2(list, 0, list.length - 1, 6);
curTime = System.nanoTime();
nsPerTime = curTime - lastTime;
System.out.print(nsPerTime / 1.0E9 + ",");
}
System.out.println();
System.out.println("MergeSort Callable");
for (listNum = delta; listNum <= maxNum; listNum += delta) {
list = RandomList(listNum);
ExecutorService threadPool = Executors.newCachedThreadPool();
MergeSort4 mergeSort4 = new MergeSort4(list, threadPool);
lastTime = System.nanoTime();
Future<Boolean> result = threadPool.submit(mergeSort4);
try {
result.get();
} catch (InterruptedException e) {
e.printStackTrace();
} catch (ExecutionException e) {
e.printStackTrace();
} finally {
threadPool.shutdown();
}
curTime = System.nanoTime();
nsPerTime = curTime - lastTime;
System.out.print(nsPerTime + ",");
}
System.out.println();
System.out.println("MergeSort RecursiveTask");
for (listNum = delta; listNum <= maxNum; listNum += delta) {
list = RandomList(listNum);
ForkJoinPool forkJoinPool = new ForkJoinPool();
MergeSort5 mergeSort5 = new MergeSort5(list);
lastTime = System.nanoTime();
Future result = forkJoinPool.submit(mergeSort5);
try {
result.get();
} catch (InterruptedException e) {
e.printStackTrace();
} catch (ExecutionException e) {
e.printStackTrace();
} finally {
forkJoinPool.shutdown();
}
curTime = System.nanoTime();
nsPerTime = curTime - lastTime;
System.out.print(nsPerTime + ",");
}
System.out.println();
}
public static Integer[] combine(Integer[] a, Integer[] b) {
ArrayList<Integer> list = new ArrayList<>(
a.length + b.length);
int i = 0;
int j = 0;
while (i < a.length && j < b.length) {
if (a[i] < b[j]) {
list.add(a[i++]);
} else {
list.add(b[j++]);
}
}
while (i < a.length) {
list.add(a[i++]);
}
while (j < b.length) {
list.add(b[j++]);
}
return list.toArray(new Integer[a.length + b.length]);
}
public static void MergeArray(
Integer[] list,
int first,
int mid,
int last) {
int i = first;
int j = mid + 1;
int m = mid;
int n = last;
ArrayList<Integer> tmp = new ArrayList<>(
last - first + 1);
while (i <= m && j <= n) {
if (list[i] <= list[j]) {
tmp.add(list[i++]);
} else {
tmp.add(list[j++]);
}
}
while (i <= m) {
tmp.add(list[i++]);
}
while (j <= n) {
tmp.add(list[j++]);
}
for (int index = 0; index < tmp.size(); index++) {
list[first + index] = tmp.get(index);
}
}
public static void MergeSort(
Integer[] list,
int first,
int last) {
if (first < last) {
int mid = (first + last) / 2;
MergeSort(list, first, mid);
MergeSort(list, mid + 1, last);
MergeArray(list, first, mid, last);
}
}
public static void MergeSort2(
Integer[] list,
int first,
int last,
int min) {
if (last - first > min) {
int mid = (first + last) / 2;
MergeSort(list, first, mid);
MergeSort(list, mid + 1, last);
MergeArray(list, first, mid, last);
} else {
BubbleSort(list, first, last);
}
}
public static void MergeSort3(
Integer[] list,
int first,
int last) {
if (last - first > 5) {
int mid = (first + last) / 2;
MergeSort(list, first, mid);
MergeSort(list, mid + 1, last);
MergeArray(list, first, mid, last);
} else {
BubbleSort(list, first, last);
}
}
public static class MergeSort4 implements Callable<Boolean> {
private ExecutorService threadPool;
private Future<Boolean> loadResult0;
private Future<Boolean> loadResult1;
private Integer[] list;
private int first;
private int last;
public MergeSort4(Integer[] list, ExecutorService threadPool) {
this.list = list;
this.threadPool = threadPool;
first = 0;
last = list.length - 1;
}
public MergeSort4(Integer[] list, int first, int last,
ExecutorService threadPool) {
this.list = list;
this.first = first;
this.last = last;
this.threadPool = threadPool;
}
/**
* Computes a result, or throws an exception if unable to do so.
*
* @return computed result
* @throws Exception if unable to compute a result
*/
@Override
public Boolean call() throws Exception {
if (last - first > 5) {
int mid = (first + last) / 2;
loadResult0 = threadPool.submit(
new MergeSort4(list, first, mid, threadPool)
);
loadResult1 = threadPool.submit(
new MergeSort4(list, mid + 1, last, threadPool)
);
try {
if (loadResult0.get() && loadResult1.get()) {
MergeArray(list, first, mid, last);
}
} catch (InterruptedException e) {
e.printStackTrace();
} catch (ExecutionException e) {
e.printStackTrace();
}
} else {
BubbleSort(list, first, last);
}
return true;
}
}
public static class MergeSort5 extends RecursiveTask {
private Integer[] list;
private int first;
private int last;
public MergeSort5(Integer[] list) {
this.list = list;
first = 0;
last = list.length - 1;
}
public MergeSort5(Integer[] list, int first, int last) {
this.list = list;
this.first = first;
this.last = last;
}
/**
* The main computation performed by this task.
*
* @return the result of the computation
*/
@Override
protected Object compute() {
if (last - first > 5) {
int mid = (first + last) / 2;
MergeSort5 leftTask = new MergeSort5(list, first, mid);
MergeSort5 rightTask = new MergeSort5(list, mid + 1, last);
leftTask.fork();
rightTask.fork();
leftTask.join();
rightTask.join();
MergeArray(list, first, mid, last);
} else {
BubbleSort(list, first, last);
}
return null;
}
}
public static class CountTask extends RecursiveTask {
private static final int THRESHOLD = 2;
private int start;
private int end;
public CountTask(int start, int end) {
this.start = start;
this.end = end;
}
/**
* The main computation performed by this task.
*
* @return the result of the computation
*/
@Override
protected Integer compute() {
int sum = 0;
boolean canCompute = (end - start) <= THRESHOLD;
if (canCompute) {
for (int i = start; i <= end; i++) {
sum += i;
}
} else {
int middle = (start + end) / 2;
CountTask leftTask = new CountTask(start, middle);
CountTask rightTask = new CountTask(middle + 1, end);
leftTask.fork();
rightTask.fork();
int leftResult = (int) leftTask.join();
int rightResult = (int) rightTask.join();
sum = leftResult + rightResult;
}
return sum;
}
}
public static Integer[] RandomList(int num) {
ArrayList<Integer> list = new ArrayList<>(num);
for (int i = 0; i < num; i++) {
list.add(i);
}
Collections.shuffle(list);
return list.toArray(new Integer[num]);
}
public static void BubbleSort(Integer[] list) {
for (int i = 0; i < list.length; i++) {
for (int j = i + 1; j < list.length; j++) {
if (list[i] > list[j]) {
swap(list, i, j);
}
}
}
}
public static void BubbleSort(
Integer[] list,
int first,
int last) {
for (int i = first; i <= last; i++) {
for (int j = i + 1; j <= last; j++) {
if (list[i] > list[j]) {
swap(list, i, j);
}
}
}
}
public static void swap(Integer[] list, int index1, int index2) {
int tmp = list[index1];
list[index1] = list[index2];
list[index2] = tmp;
}
}