排序快查
首先
交换两个数字的三种方式：
Q:交换 x 和 y 的值
1. 添加第三个变量辅助交换
int temp = x;
x = y;
y = temp;
2. 不使用辅助变量交换
x = x + y;
y = x - y;
x = x - y;
3. 使用异或运算交换
x = x ^ y;
y = x ^ y;
x = x ^ y;
4. 简单交换一下
x = (x + y) - (y = x);
1. 冒泡排序
排序思想：
将数组中两个数从前到后两两进行比较，较大的放到后面（前面），依次排到数组末尾。此时数组中最大的数字就已经排到了数组末尾。当一个数组中有n个元素时，我们只需要进行n-1次这样的操作既可以将整个数组排序。
将数组中最大的数字通过冒泡的方式冒出来。
动图演示：
冒泡排序动态演示
代码书写：
public void bubble_sort(int[] arr, int len)
{
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 temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
2.快速排序
排序思想：
选取数组中一个点作为基准值，遍历数组，所有比基准值小的元素放置在基准值的左边，所有比基准值大的元素放置在基准值的右边，完成第一趟排序。然后对先后两个序列分别进行上述相同的排序方式，直到数组排好序。
动图演示：
快速排序动态演示
代码书写：
public static void QuickSort(int[] arr)
{
if (arr.length > 0) {
QuickSubSort(arr, 0, arr.length - 1);
}
}
private static void QuickSubSort(int[] arr, int start, int end)
{
if(start >= end){
return;
}
int left = start;
int right = end;
int key = arr[left]; // 选取数组第一个元素作为基准值
while (left < right){ // 数组遍历直到前后两个指针相遇，表示一次排序完成
// 从右往左找到第一个小于基准值的数字
while (left < right && arr[right] >= key){
right--;
}
// 从左往右找到第一个大于基准值的数字
while (left < right && arr[left] <= key){
left++;
}
// 交换两个数字位置
if(left<right){
arr[left] = arr[left]^arr[right];
arr[right] = arr[left]^arr[right];
arr[left] = arr[left]^arr[right];
}
}
// 交换基准值与中间值的位置
arr[start] = arr[left];
arr[left] = key;
// 分区递归进行上述排序
QuickSubSort(arr,start,left-1);
QuickSubSort(arr,left+1,end);
}
3. 插入排序
排序思想：
选择一个已经排好序的序列，将新的数字插入到排序完成的序列的适当位置，构成一个新的排序完成的序列。一般我们从第一个数字开始，一个数字的序列默认就是已经排好序的序列。
动图演示：
插入排序动图演示
代码书写：
public static void InsertSort(int[] arr){
for(int i=1;i<arr.length;i++){
int temp = arr[i]; // 当前需要插入的数字
int j;
for(j=i-1;j>=0;j--){ // 找到需要插入的位置，数字依次后移
if(temp < arr[j]){
arr[j+1] = arr[j];
}else{
break;
}
}
arr[j+1] = temp; // 将数字插入到指定的位置
}
}
4. 希尔排序
算法思想：
先将整个待排记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，在对全体进行一次直接插入排序。
希尔排序需要先确定增量的值，然后逐渐缩小增量的值直到增量为一，当增量为一时即为直接插入排序。
动图演示：
希尔排序动图演示
代码书写：
public void ShellSort(int[] arr)
{
int len = arr.length;
int increment = arr.length;
while (increment > 1) {
increment = increment / 3 + 1; // 步长公式
// 步长为 increment 的直接插入排序
for (int i = increment; i < len; i++) {
int temp = arr[i];
int j;
for(j=i-increment; j>=0; j-=increment){
if(temp < arr[j]){
arr[j+increment] = arr[j];
}else{
break;
}
}
arr[j+increment] = temp;
}
}
}
5. 选择排序
排序思想：
选择数组中最小的元素放置在数组开头，然后选择次大的数放置在最小的数字之后，依次排序，直到所有元素排序完成。
动图演示：
选择排序动图演示
代码书写：
public void SelectSort(int[] arr)
{
if (arr.length > 0) {
int minindex;
for (int i = 0; i < arr.length; i++) {
minindex = i;
for (int j = i; j < arr.length; j++) {
if (arr[j] < arr[minindex]) {
minindex = j; // 找到数组中最小值
}
}
if(i!=minindex){ // 当最小值不为当前值时交换两个值
arr[i] = arr[i] ^ arr[minindex];
arr[minindex] = arr[i] ^ arr[minindex];
arr[i] = arr[i] ^ arr[minindex];
}
}
}
}
6. 堆排序
排序思想：
使用堆这个数据结构来进行排序，通常是将待排序的数字组成最大堆或者最小堆来进行排序。
动态演示：
堆排序动态演示
代码书写：
public static void HeapSort(int[] a) {
int len = a.length;
for (int i = 0; i < len - 1; i++) {
// 建堆
buildHeap(a, len - 1 - i);
// 交换堆顶元素和最后一个元素
swap(a, 0, len - 1 - i);
}
}
private static void swap(int[] a, int i, int j) {
int tmp = a[i];
a[i] = a[j];
a[j] = tmp;
}
public static void buildHeap(int[] a, int lastIndex) {
// 从最后一个节点的父节点开始
for (int i = (lastIndex - 1) / 2; i >= 0; i--) {
// 当前节点存在子节点
while (i * 2 + 1 <= lastIndex) {
// 左节点下标值
int l = i * 2 + 1;
// 右结点下标值
int r = i * 2 + 2;
// 默认左节点为最大值
int biggerIndex = l;
// 存在右结点
if (l < lastIndex) {
// 右结点的值比左节点大
if (a[r] > a[l]) {
biggerIndex = r;
}
}
// 当前节点的值比孩子节点的最小值小，交换
if (a[i] < a[biggerIndex]) {
swap(a, i, biggerIndex);
// 把最大值下标赋给当前节点，进入下一次while循环判断
i = biggerIndex;
} else {
break;
}
}
}
}
7. 归并排序
排序思想：
将已排序的子序列进行合并，合并已排序的子序列称为新的子序列。
若是合并两个子序列为新的子序列称为二路归并。
若是合并多个子序列为新的子序列称为多路归并。
- 将数组分为两个子序列，每个子序列的长度为n/2
- 对每一个子序列都采取同样的操作，直到子序列的长度为1
- 将两个排好序的子序列合并为一个序列
动图演示：
归并排序动图演示
代码书写：
public static void MergeSort(int[] arr){
int[] temp = new int[arr.length];
sort(arr,0,arr.length-1,temp);
}
private static void sort(int[] arr,int left, int right,int[] temp){
if(left<right){
int mid = (left + right) >> 1;
sort(arr,left,mid,temp); // 左子序列有序化
sort(arr,mid+1,right,temp); // 右子序列有序化
merge(arr,left,mid,right,temp); // 合并左右子序列
}
}
private static void merge(int[] arr, int left, int mid, int right, int[] temp){
int p_left = left; // 左子序列指针
int p_right = mid+1; // 右子序列指针
int p_temp = 0; // 临时数组指针
while (p_left <= mid && p_right <= right){
// 按照数字的大小顺序存放到临时数组中
if(arr[p_left] < arr[p_right]){
temp[p_temp++] = arr[p_left++];
}else{
temp[p_temp++] = arr[p_right++];
}
}
while (p_left <= mid){
temp[p_temp++] = arr[p_left++];
}
while (p_right <= right){
temp[p_temp++] = arr[p_right++];
}
p_temp = 0;
// 拷贝临时数组数据到原始数组中
while (left <= right){
arr[left++] = temp[p_temp++];
}
}
8. 基数排序
排序思想：
首先将数组中的元素按照最低位进行排序，排序后的结果按照倒数第二位进行排序，依次类推，直到排序到最高位，那么排序完成后的数组即为顺序顺组。
动图演示：
基数排序动图演示
代码书写：
十进制基数排序
/**
* 基数排序链表结点
*/
private static class Node
{
int value;
Node next;
public Node(int value, Node next)
{
this.value = value;
this.next = next;
}
public Node()
{
this.value = 0;
this.next = null;
}
}
public static void RadixSort(int[] arr)
{
// 计算数字最大值 进而确定数字最大长度
int max = 0;
for (int i = 0; i < arr.length; i++) {
max = max < arr[i] ? arr[i] : max;
}
// 基数 + 基数链表数组
int base = 1;
Node[] buckets = new Node[10];
// 循环依次按照当前位数字高低位进行排序
for (int i = 0; i < String.valueOf(max).length(); i++) {
for (int ind = 0; ind < arr.length; ind++) {
// y 为当前进行判断的位数字
int y = 0;
if (arr[ind] >= base) {
y = arr[ind] / base % 10;
}
// 把符合要求的数字放入对应的桶中
if (buckets[y] == null) {
buckets[y] = new Node(arr[ind], null);
} else {
Node node = buckets[y];
while (node.next != null) {
node = node.next;
}
node.next = new Node(arr[ind], null);
}
}
// 扩大基数
base *= 10;
// 将链表数据导出到数组
int index = 0;
for (int x = 0; x < buckets.length; x++) {
if (buckets[x] != null) {
Node node = buckets[x];
while (node != null) {
arr[index++] = node.value;
node = node.next;
}
}
}
// 清空链表数据
for (int x = 0; x < buckets.length; x++) {
buckets[x] = null;
}
}
}
参考:https://www.cnblogs.com/onepixel/articles/7674659.html
图片来自于：https://www.cnblogs.com/onepixel/articles/7674659.html
网友评论