将待排序的一组数分为有序区间和无序区间。先在无序区间通过相邻数的比较，将无序区间的最大数依次冒泡到最上面，持续这个过程，直到整组数有序。
2、图解分析以[3, 0, 5, 4, 1, 2]为例，进行冒泡排序。
第一趟：从下往上依次两两比较，将最大数交换到最上面，第一趟完成后橙色部分为已排好的部分。
第二趟：比较方法同上，橙色部分为排好的区间，我们发现有序区间比第一趟的有序区间多一个数。
第三趟：
第四趟：
第五趟：
最后排好的整组数：
我们发现，每次排好序的区间数的个数都比前一趟多一个，所以待排序的6个数共循环了5次。
3、代码实现public static void bubbleSort(int[] arr) {
//外层循环（数组长度-1）次
for (int i = 0; i < arr.length - 1; i++) {
//内层循环，有序区间不用再循环
for (int j = 0; j < arr.length - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
int tmp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = tmp;
}
}
}
}依次将待排序中的数字直接插入到已按从小到大（或者从大到小）排好的序列中去，直到插完所有数字为止。
2、图解分析 3、代码实现public static void insertSort(int[] arr) {
for (int i = 1; i < arr.length; i++) {
int tmp = arr[i]; //记录待排序中的第一个数
int j = i - 1; //[1,i)为排序好的，[i,arr.length)是待排序的
for (j = i - 1; j >= 0; j--) { //遍历已排序的数
if (arr[j] > tmp) { //如果已排序中当前数字大于待排序的数字
arr[j + 1] = arr[j]; //依次将已排序的数字往后移一位
} else {
break;
}
}
arr[j + 1] = tmp; //arr[j]的大小<待排序tmp，因此将tmp放在arr[j+1]
}
}第一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后再从剩余的未排序元素中寻找到最小（大）元素，然后放到已排序的序列的末尾。以此类推，直到全部待排序的数据元素的个数为零。
2、图解分析如图，将整个序列分为有序序列和无序序列。蓝色部分是每次进行比较的内容，将相对小的数字交换到前面；黄色部分则是已排好的序列。
3、代码实现public static void selectSort(int[] arr) {
//[0,i)是已排序区间，[i,arr.length)是待排序区间
for (int i = 0; i < arr.length - 1; i++) {
for (int j = i + 1; j < arr.length; j++) {
//先遍历找到待排序区间最小的数
//i位置的数就是待比较的数
if (arr[i] > arr[j]) {
//i位置的数大，就交换
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
}
}
}- 从待排序区间选择一个数，作为基准值(index)；
- Partition: 遍历整个待排序区间，将比基准值小的（可以包含相等的）放到基准值的左边，将比基准值大的（可以包含相等的）放到基准值的右边；
- 采用分治思想，对左右两个小区间按照同样的方式处理，直到小区间的长度 == 1，代表已经有序，或者小区间的长度 == 0，代表没有数据。
（1）以{1, 3, 6, 5, 0, 2}为例，将较小的数换在左边，反之在右边。
将最右边的数作为基准值，right先从右边向左找第一个比基准值2小的数，找到为0；left再从左边向右找第一个比基准值大的数，找到为3，交换这两个数。
（2）
在（1）的基础上，right先走，从右往左找第一个比基准值2小的数，我们发现，此时right和left相遇了，将相遇的值与基准值2比较，相遇的值比基准值大，所以我们交换两个数。
（3）
现在，第一趟比较已经结束，数字2相当于已经归位了，所以我们以2为分界线，分别比较2左边的数和2右边的数，比较方法和上面的一样。最后我们会得到一组有序的数。
3、代码实现public static void quikSort(int[] arr) {
quikHelpSort(arr, 0, arr.length - 1);
}
private static void quikHelpSort(int[] arr, int left, int right) {
if (left >= right) {
return;
}
int index = partition(arr, left, right); //当前基准值的位置
quikHelpSort(arr, left, index -1);
quikHelpSort(arr, index + 1, right);
}
private static int partition(int[] arr, int left, int right) {
int num = right; //基准值的位置，一趟排序走完，基准值位置确定
while (left < right) {
//先从右往左找到第一个比num小的数
while (arr[right] > arr[num] && left < right) {
right--;
}
//从左往右找到第一个比num大的数
while (arr[left] < arr[num] && left < right) {
left++;
}
//交换这两个数
swap(arr, left, right);
}
//left和right相遇，交换基准值和相遇的值，所以这里写left或者right都可以
swap(arr, right, num);
return left;
}
public static void swap (int[] arr, int i, int j) {
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}希尔排序法又称缩小增量法。是插入排序的优化。
希尔排序法的基本思想是：先选定一个整数，把待排序文件中所有记录分成一个组，所有距离为一样的记录分在同一组内，并对每一组内的记录进行排序。然后取整数一半的值，重复上述分组和排序的工作。当值到达1时，所有记录在同一组内排好序。
2、图解分析（1）将整个数组分组gap=arr.length/2;如图颜色一样的为一组。（按从小到大排序）
（2）将颜色一样的值进行比较，小的换到前面，大的换到后面；再进行分组gap=gap/2,如图颜色一样的为一组。
（3）重复上述步骤。
（4）最终排好的序列如图。
3、代码实现public static void shellSort(int[] arr) {
int gap = arr.length;
while (gap > 1) {
gap = gap / 2;
insertGap(arr, gap);
}
insertGap(arr, 1);
}
private static void insertGap(int[] arr, int gap) {
for (int i = 1; i < arr.length; i++) {
int tmp = arr[i];
int j = i - gap;
for (j = i - gap; j >= 0; j -= gap) {
if (arr[j] > tmp) {
arr[j + gap] = arr[j];
} else {
break;
}
}
arr[j + gap] = tmp;
}
}归并排序（MERGE-SORT）是建立在归并 *** 作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。
2、图解分析先将无序数组分割，经过排序，将两个有序数组再拼接。实质就是合并两个有序数组。
3、代码实现public static void mergeSort(int[] arr) {
mergeSortHelp(arr, 0, arr.length - 1);
}
private static void mergeSortHelp(int[] arr, int start, int end) {
if (start < end) {
int mid = (start + end) / 2;
mergeSortHelp(arr, start, mid);
mergeSortHelp(arr, mid + 1, end);
merge(arr, start, mid, end);
}
}
//合并两个有序数组
private static void merge(int[] arr, int left, int mid, int right) {
int[] tmp = new int[arr.length]; //辅助数组
int p1 = left, p2 = mid + 1, k = left;
while (p1 <= mid && p2 <= right) {
if (arr[p1] <= arr[p2]) {
tmp[k++] = arr[p1++];
} else {
tmp[k++] = arr[p2++];
}
}
while (p1 <= mid) tmp[k++] = arr[p1++]; //如果第一个序列未检测完，直接将后面所有元素加到合并的序列中
while (p2 <= right) tmp[k++] = arr[p2++];
//复制回原数组
for (int i = left; i <= right; i++) {
arr[i] = tmp[i];
}
}堆排序的基本原理也是选择排序，只是不在使用遍历的方式查找无序区间的最大的数，而是通过堆来选择无序区间的最大的数。
2、图解分析（1）建堆（这里是以建大顶堆为例）
先把数组中的数转换成二叉树的形式，在这个基础上建堆。这里用到的大顶堆的性质：所有父节点的值要大于其子节点的值。按照这个性质，将无序的二叉树调整成堆。
父节点和子节点计算：
如图是一个简易的二叉树，蓝色的数字为节点的序号。计算父节点的序号要根据已知的子节点的序号求得。假设当前孩子节点的序号为 i ，那么这个节点的父节点 = ( i - 1 ) / 2。不管当前节点是右孩子节点还是左孩子节点，这个都是成立的。
计算子节点的序号则是根据父节点的序号求得。假设父节点的序号为 i ，左孩子节点的序号 = ( 2 i ) + 1，右孩子节点的序号 = ( 2 i ) + 2。
（2）运用堆进行排序
建大顶堆就是将数字按升序排列。建好大顶堆后，此时大顶堆堆顶的值就是最大值，将堆顶元素与最后一个节点交换，最后的这个节点就是排序好的值，节点前面的值再进行建大顶堆，这里再建堆就不再包含已经排序好的节点了，依次类推，直到排序完成。
3、代码实现public static void heapSort(int[] arr, int n) {
//n 表示数组的个数，即原始数组的长度
buildHeap(arr);
for (int i = n - 1; i > 0; i--) {
swap(arr, 0, i);//将最大值交换到当前数组的最后面，交换之后[0,i)区间是无序的，[i,n)是有序的
adjust(arr, i, 0);//再调整[0,i)区间，直到排序完成
}
}
private static void buildHeap(int[] arr) {
int last_node = arr.length - 1; //最后一个节点的序号
int parent = (last_node - 1) / 2; //找出最后一个节点的父节点，目的是为了从最后一个小堆开始调整
for (int i = parent; i >= 0; i--) { //从下往上依次调整
adjust(arr, arr.length, i);
}
}
private static void adjust(int[] arr, int n, int i) {
//n表示数组的个数，即原始数组的长度，i表示节点的序号
if (i >= n) {
return;
}
int left = 2 * i + 1; //左孩子节点
int right = 2 * i + 2; //右孩子节点
int max = i; //先令最大值为父节点的值，后面再比较父节点和两个孩子结点的值，找出最大值
if (left < n && arr[left] > arr[max]) {
max = left;
}
if (right < n && arr[right] > arr[max]) {
max = right;
}
if (max != i) { //当最大值不是父节点的时候，就将最大值和父节点交换
swap(arr, max, i);
adjust(arr, n, max); //用递归进行调整
}
}
public static void swap (int[] arr, int i, int j) {
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）