基本排序算法(冒泡排序 选择排序 插入排序 快速排序 归并排序 基数排序 希尔排序)

时间:2022-02-05 22:07:50

项目地址:https://github.com/windwant/algorithm-test.git

冒泡排序:

public static void bubbleSort(int[] arr){
int lgn = arr.length;
for (int i = 0; i < lgn - 1; i++) {
for (int j = 0; j < lgn - 1 - i; j++) {
if(arr[j] > arr[j + 1]){
int temp = arr[j + 1];
arr[j
+ 1] = arr[j];
arr[j]
= temp;
}
}
}
}

选择排序:

public static void SelectionSort(int[] arr){
for (int i = 0; i < arr.length; i++) {
for (int j = i + 1; j < arr.length ; j++) {
if(arr[j] < arr[i]){
int temp = arr[i];
arr[i]
= arr[j];
arr[j]
= temp;
}
}
}
}

插入排序:

public static void insertionSort(int [] array){
for(int i = 1; i < array.length; i++){
int temp = array[i];//被标记的值或者说是当前需要插入的值
int j = i;
//如果轮循值大于被标记值则往后移
while( j > 0 && temp < array[j - 1]){
array[j]
= array[j - 1];
j
-- ;
}
//将被标记值插入最终移出的空位置
array[j] = temp;
}
}

快速排序:

public static void quikeSort(int[] arr, int low, int high) {
int start = low;
int end = high;
int anchor = arr[low];

while (end > start) {
//比较 anchor---end
while (end > start && arr[end] >= anchor) { //从末尾向前寻找小于等于anchor的值
end--;
}

//交换位置
if (arr[end] <= anchor) {
int temp = arr[end];
arr[end]
= arr[start];
arr[start]
= temp;
}

//比较start---anchor
while (end > start && arr[start] <= anchor) {//从起始位置向后寻找大于等于anchor的值
start++;
}

//交换位置
if (arr[start] >= anchor) {
int temp = arr[start];
arr[start]
= arr[end];
arr[end]
= temp;
}
}
//anchor位置确定。左边的元素值都小于anchor值,右边的值都大于anchor值,递归排序左右两侧排序
//左边元素。low---anchor值索引-1
if (start > low) {
quikeSort(arr, low, start
- 1);
}

//右边元素。从anchor值索引+1---high
if (end < high) {
quikeSort(arr, end
+ 1, high);
}
}

归并排序:

public static void mergeSort(int[] data) {
sort(data,
0, data.length - 1);
}

public static void sort(int[] data, int left, int right) {
if (left >= right)
return;
// 找出中间索引
int center = (left + right) / 2;
// 对左边数组进行递归
sort(data, left, center);
// 对右边数组进行递归
sort(data, center + 1, right);
// 合并
merge(data, left, center, right);
}

/**
* 将两个数组进行归并,归并前面2个数组已有序,归并后依然有序
*
*
@param data
* 数组对象
*
@param left
* 左数组的第一个元素的索引
*
@param center
* 左数组的最后一个元素的索引,center+1是右数组第一个元素的索引
*
@param right
* 右数组最后一个元素的索引
*/
public static void merge(int[] data, int left, int center, int right) {
// 临时数组
int[] tmpArr = new int[data.length];
// 右数组第一个元素索引
int mid = center + 1;
// third 记录临时数组的索引
int third = left;
// 缓存左数组第一个元素的索引
int tmp = left;
while (left <= center && mid <= right) {
// 从两个数组中取出最小的放入临时数组
if (data[left] <= data[mid]) {
tmpArr[third
++] = data[left++];
}
else {
tmpArr[third
++] = data[mid++];
}
}
// 剩余部分依次放入临时数组(实际上两个while只会执行其中一个)
while (mid <= right) {
tmpArr[third
++] = data[mid++];
}
while (left <= center) {
tmpArr[third
++] = data[left++];
}
// 将临时数组中的内容拷贝回原数组中
// (原left-right范围的内容被复制回原数组)
while (tmp <= right) {
data[tmp]
= tmpArr[tmp++];
}
}

基数排序:

//LSD
public static void radixLSDSort(int[] arr){
//最高位数
int maxBit = getMaxBit(arr);
//十个bulk 分别存放 每个位数 数字 相应的元素 如个位为3 则放入bulk[3]
Queue<Integer>[] bulk = new Queue[10];
for (int i = 0; i < bulk.length; i++) {
bulk[i]
= new ArrayDeque();
}
//分别处理不同位数 存放 处理
for (int i = 0; i < maxBit; i++) {
for (int j = 0; j < arr.length; j++) {
int ivalue = (int) (arr[j] % Math.pow(10, i + 1) / Math.pow(10, i)); //去相应位数上的数字作为 存入bulk index
bulk[ivalue].offer(arr[j]);
}

//取出bulk中的元素 重新放入数组 并清除bulk中的元素。
int arrIndex = 0;
for (int j = 0; j < bulk.length; j++) {
while (bulk[j].size()>0){
arr[arrIndex
++] = bulk[j].poll();
}
}
}
}

public static int getMaxBit(int[] arr){
int max = arr[0];
for (int i = 1; i < arr.length; i++) {
if(arr[i] > max){
max
= arr[i];
}
}

int b = 0;
while (max > 0){
max
/= 10;
b
++;
}
return b;
}

public static void radixMSDSort(int[] arr){
msdSort(arr,
0, arr.length, getMaxBit(arr));
}

//MSD
public static void msdSort(int[] arr, int left, int right, int maxBit){
//十个bulk 分别存放 每个位数 数字 相应的元素 如个位为3 则放入bulk[3]
Queue<Integer>[] bulk = new Queue[10];
for (int i = 0; i < bulk.length; i++) {
bulk[i]
= new ArrayDeque();
}
//依据最高位分别放入不同的bulk
for (int j = left; j < right; j++) {
int ivalue = (int) (arr[j] % Math.pow(10, maxBit) / Math.pow(10, maxBit - 1)); //去相应位数上的数字作为 存入bulk index
bulk[ivalue].offer(arr[j]);
}

//取出bulk中的元素 重新放入数组 并清除bulk中的元素。记录bulk中queue大小大于1的数组索引 递归使用
List<Integer> count = new ArrayList<Integer>();
int arrIndex = left;
for (int j = 0; j < bulk.length; j++) {
int start = arrIndex;
while (bulk[j].size()>0){
arr[arrIndex
++] = bulk[j].poll();
}
if(arrIndex - start > 1){
count.add(start);
count.add(arrIndex);
}
}
//递归最小位判断
int nextBit = maxBit - 1;
if(nextBit > 0) {
for (int i = 1; i < count.size(); i += 2) {
msdSort(arr, count.get(i
- 1), count.get(i), nextBit);
}
}
}

shell排序:

public static void shellSort(int[] arr){
int step = arr.length/2;
while (step >= 1) { //步长为1时 包含所有数组序列
for (int i = 0; i < step; i++) { //步长为n则数组将分为n组分别排序
for (int j = step + i; j < arr.length; j += step) { //对跨步长每组元素进行插入排序
int temp = arr[j];
int preIndex = j - step;
while (preIndex > -1 && temp < arr[preIndex]) {
arr[preIndex
+ step] = arr[preIndex];
preIndex
-= step;
}
arr[preIndex
+ step] = temp;
System.out.println(
" middle: " + Arrays.toString(arr));
}
}
step
/= 2; //每次步长处理
}
}