前言:
而今看官们对“首次适应算法java实现什么”大体比较珍视,看官们都需要分析一些“首次适应算法java实现什么”的相关内容。那么小编同时在网络上收集了一些有关“首次适应算法java实现什么””的相关知识,希望你们能喜欢,大家一起来学习一下吧!内容简介:冒泡、快排等十大排序算法原理及java实现
相关链接:无
背景:无
hi,小伙伴们,咱们这篇文章总结下常用的十大排序算法
一、前言
1-分类
十种常见排序算法可以分为两大类:
比较类排序:通过比较来决定元素间的相对次序,由于其时间复杂度不能突破O(nlogn),因此也称为非线性时间比较类排序。
非比较类排序:不通过比较来决定元素间的相对次序,它可以突破基于比较排序的时间下界,以线性时间运行,因此也称为线性时间非比较类排序。
2-复杂度
二、算法
(一)插入排序(Insertion-Sort)是对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。
1-实现步骤
步骤1: 从第一个元素开始,前面的数据被认为是已经排好序的;
步骤2: 取出下一个元素,在已经排序的序列中从后向前扫描;
步骤3: 如果该元素(已排序)大于新元素,将该元素移到下一位置;
步骤4: 重复步骤3,直到找到已排序的元素小于或者等于新元素的位置;
步骤5: 将新元素插入到该位置后;
步骤6: 重复步骤2~5
2-算法分析
最佳情况:T(n) = O(n)
最坏情况:T(n) = O(n2)
平均情况:T(n) = O(n2)
3-算法实现(java)
public void insertSort(int[] a) {
int len = a.length;//单独把数组长度拿出来,提高效率
int insertNum;//要插入的数
for (int i = 1; i < len; i++) {//因为第一次不用,所以从1开始
insertNum = a[i];
int j = i - 1;//序列元素个数
while (j >= 0 && a[j] > insertNum) {//从后往前循环,将大于insertNum的数向后移动
a[j + 1] = a[j];//元素向后移动
j--;
}
a[j + 1] = insertNum;//找到位置,插入当前元素
}
}
(二)希尔排序-是插入排序改进后的版本,它与插入排序的不同之处在于,它会优先比较距离较远的元素。
它是将数组按照len间隔分成多个数组,每个数组再执行直接插入排序
1-实现步骤
步骤1:按照len间隔分组,len/2
步骤2:对每个组实行直接插入排序
2-算法分析
最佳情况:T(n) = O(nlog2 n)
最坏情况:T(n) = O(nlog2 n)
平均情况:T(n) =O(nlog2n)
3-算法实现(java)
public void sheelSort(int[] a) {
int len = a.length;//单独把数组长度拿出来,提高效率
int insertNum;
while (len != 0) {
len = len / 2;
for (int g = 0; g < len; g++) {//分组
for (int i = g + len; i < a.length; i += len) {//元素从第二个开始
insertNum = a[i];//要插入的元素
int j = i - len;//k为有序序列最后一位的位数
while (j >= 0 && a[j] > insertNum) {//从后往前遍历
a[j + len] = a[j];
j -= len;//向前移动len位
}
a[j + len] = insertNum;//因为是已经减了len,所以要加上
}
}
}
}
(三)选择排序-首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置,然后,再从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾。以此类推,直到所有元素均排序完毕。
1-实现步骤
步骤1:遍历整个序列,将最小的数放在最前面。
步骤2:遍历剩下的序列,将最小的数放在最前面。
步骤3:重复第二步,直到只剩下一个数。
2-算法分析
最佳情况:T(n) = O(n2)
最差情况:T(n) = O(n2)
平均情况:T(n) = O(n2)
3-算法实现(java)
public void selectSort(int[] a) {
int len = a.length;
for (int i = 0; i < len; i++) {//循环次数
int min = a[i];
int minPosition = i;
for (int j = i + 1; j < len; j++) {//找到最小的值和位置
if (a[j] < min) {
min = a[j];
minPosition = j;
}
}
a[minPosition] = a[i];//进行交换
a[i] = min;
}
}
(四)堆排序
1-实现步骤
步骤1:将初始待排序关键字序列(R1,R2….Rn)构建成大顶堆,此堆为初始的无序区;
步骤2:将堆顶元素R[1]与最后一个元素R[n]交换,此时得到新的无序区(R1,R2,……Rn-1)和新的有序区(Rn),且满足R[1,2…n-1]<=R[n];
步骤3:由于交换后新的堆顶R[1]可能违反堆的性质,因此需要对当前无序区(R1,R2,……Rn-1)调整为新堆,然后再次将R[1]与无序区最后一个元素交换,得到新的无序区(R1,R2….Rn-2)和新的有序区(Rn-1,Rn)。不断重复此过程直到有序区的元素个数为n-1,则整个排序过程完成。
2-算法分析
最佳情况:T(n) = O(nlogn)
最差情况:T(n) = O(nlogn)
平均情况:T(n) = O(nlogn)
3-算法实现(java)
public void heapSort(int[] arr) {
for (int i = arr.length / 2 - 1; i >= 0; i--) {/*第一个非叶子结点 arr.length/2-1*/
//从第一个非叶子结点从下至上,从右至左调整结构
buildMaxHeap(arr, i, arr.length);
}
//2.调整堆结构+交换堆顶元素与末尾元素
for (int j = arr.length - 1; j > 0; j--) {
swap(arr, 0, j);//将堆顶元素与末尾元素进行交换
buildMaxHeap(arr, 0, j);//重新对堆进行调整
}
}
//交换方法
private void swap(int[] data, int i, int j) {
int tmp = data[i];
data[i] = data[j];
data[j] = tmp;
}
//对data数组从0到lastIndex建大顶堆
private void buildMaxHeap(int[] arr, int i, int length) {
int temp = arr[i];//先取出当前元素i
for (int k = i * 2 + 1; k < length; k = k * 2 + 1) {//从i结点的左子结点开始,也就是2i+1处开始
if (k + 1 < length && arr[k] < arr[k + 1]) {//如果左子结点小于右子结点,k指向右子结点
k++;
}
if (arr[k] > temp) {//如果子节点大于父节点,将子节点值赋给父节点(不用进行交换)
arr[i] = arr[k];
i = k;
} else {
break;
}
}
arr[i] = temp;//将temp值放到最终的位置
}
(五)冒泡排序。它重复遍历要排序的数列,一次比较两个元素,如果它们的顺序错误就把它们交换过来。类似烧开水时,壶底的水泡往上冒的过程
1-实现步骤
步骤1:从第一个数开始,依次往后比较,如果前面的数比后面的数大就交换,否则不作处理。
步骤2: 针对所有的元素重复以上的步骤,除了最后一个;
步骤3:重复步骤1~2,直到排序完成。
2-算法分析
最佳情况:T(n) = O(n)
最差情况:T(n) = O(n2)
平均情况:T(n) = O(n2)
3-算法实现(java)
一个数与全部的比完之后,再进行下一轮 ***/
public void bubbleSort(int[] a) {
int len = a.length;
for (int i = 0; i < len; i++) {
for (int j = 0; j < len - i - 1; j++) {//注意第二重循环的条件,因为肯定最大的一个已经到队尾了,就不用再比较了
if (a[j] > a[j + 1]) {
int temp = a[j];
a[j] = a[j + 1];
a[j + 1] = temp;
}
}
}
}
(六)快速排序-选择第一个数为p,小于p的数放在左边,大于p的数放在右边。递归的将p左边和右边的数都按照第一步进行,直到不能递归。
1-实现步骤
步骤1:选择一个基准,常为第一个数,
步骤 2:right、left依次走动
步骤3:如果找到,则交换
步骤4:left=right时,交换基准值和这个值
步骤5:递归左和右两组
2-算法分析
最佳情况:T(n) = O(nlogn)
最差情况:T(n) = O(n2)
平均情况:T(n) = O(nlogn)
3-算法实现(java)
public void quickSort(int[] a, int start, int end) {
if (start > end)
return;
int left, right, temp;
temp = a[start]; //temp中存的就是基准数
left = start;
right = end;
while (left != right) {
//顺序很重要,要先从右边开始找,否则有可能在与基准交换的时候将大于基准的数交换了
while (a[right] >= temp && left < right)
right--;
//再找右边的
while (a[left] <= temp && left < right)
left++;
//交换两个数在数组中的位置
if (left < right) {
swap(a, left, right);
}
}
//最终将基准数归位
swap(a, start, left);
quickSort(a, start, left - 1);//继续处理左边的,这里是一个递归的过程
quickSort(a, left + 1, end);//继续处理右边的 ,这里是一个递归的过程
}
(七)归并排序-把前一半排序,把后一半排序,最后把两半归并到一个新的有序数组,最后拷贝到原数组
1-实现步骤
步骤1:把长度为n的输入序列分成两个长度为n/2的子序列;
步骤2:对这两个子序列分别采用归并排序;
步骤3:将两个排序好的子序列合并成一个最终的排序序列
2-算法分析
最佳情况:T(n) = O(n)
最差情况:T(n) = O(nlogn)
平均情况:T(n) = O(nlogn)
3-算法实现(java)
public void mergeSort(int[] a, int start, int end) {
if (start >= end) {
return;
}
int mid = start + (end - start) / 2;
mergeSort(a, start, mid);
mergeSort(a, mid + 1, end);
merge(a, start, mid, end);
}
private static void merge(int[] a, int start, int mid, int end) {
int pTemp = 0;
int[] temp = new int[end - start + 1];
int p1 = start, p2 = mid + 1;
while (p1 <= mid && p2 <= end) {
if (a[p1] < a[p2])
temp[pTemp++] = a[p1++];
else
temp[pTemp++] = a[p2++];
}
while (p1 <= mid) {
temp[pTemp++] = a[p1++];
}
while (p2 <= end) {
temp[pTemp++] = a[p2++];
}
System.arraycopy(temp, 0, a, start + 0, temp.length);
}
基数排序: 根据键值的每位数字来分配桶
计数排序: 每个桶只存储单一键值
桶排序: 每个桶存储一定范围的数值
(八)计数排序-使用一个额外的数组C,其中第i个元素是待排序数组A中值等于i的元素的个数。然后根据数组C来将A中的元素排到正确的位置。
1-实现步骤
步骤1:找出待排序的数组中最大和最小的元素;
步骤2:统计数组中每个值为i的元素出现的次数,存入数组C的第i项;
步骤3:对所有的计数累加(从C中的第一个元素开始,每一项和前一项相加);
步骤4:反向填充目标数组:将每个元素i放在新数组的第C(i)项,每放一个元素就将C(i)减去1。
2-算法分析
最佳情况:T(n) = O(n+k)
最差情况:T(n) = O(n+k)
平均情况:T(n) = O(n+k)
3-算法实现(java)
public int[] countingSort(int[] array) {
if (array.length == 0) return array;
int bias, min = array[0], max = array[0];
for (int i = 1; i < array.length; i++) {
if (array[i] > max)
max = array[i];
if (array[i] < min)
min = array[i];
}
bias = 0 - min;
int[] bucket = new int[max - min + 1];
Arrays.fill(bucket, 0);
for (int i = 0; i < array.length; i++) {
bucket[array[i] + bias]++;
}
int index = 0, i = 0;
while (index < array.length) {
if (bucket[i] != 0) {
array[index] = i - bias;
bucket[i]--;
index++;
} else
i++;
}
return array;
}
(九)桶排序- 是计数排序的升级版。假设输入数据服从均匀分布,将数据分到有限数量的桶里,每个桶再分别排序(有可能再使用别的排序算法或是以递归方式继续使用桶排序进行
1-实现步骤
步骤1:人为设置一个BucketSize,作为每个桶所能放置多少个不同数值(例如当BucketSize==5时,该桶可以存放{1,2,3,4,5}这几种数字,但是容量不限,即可以存放100个3);
步骤2:遍历输入数据,并且把数据一个一个放到对应的桶里去;
步骤3:对每个不是空的桶进行排序,可以使用其它排序方法,也可以递归使用桶排序;
步骤4:从不是空的桶里把排好序的数据拼接起来。
2-算法分析
最佳情况:T(n) = O(n+k)
最差情况:T(n) = O(n+k)
平均情况:T(n) = O(n2)
3-算法实现(java)
public ArrayList<Integer> BucketSort(ArrayList<Integer> array, int bucketSize) {
if (array == null || array.size() < 2)
return array;
int max = array.get(0), min = array.get(0);
// 找到最大值最小值
for (int i = 0; i < array.size(); i++) {
if (array.get(i) > max)
max = array.get(i);
if (array.get(i) < min)
min = array.get(i);
}
int bucketCount = (max - min) / bucketSize + 1;
ArrayList<ArrayList<Integer>> bucketArr = new ArrayList<>(bucketCount);
ArrayList<Integer> resultArr = new ArrayList<>();
for (int i = 0; i < bucketCount; i++) {
bucketArr.add(new ArrayList<Integer>());
}
for (int i = 0; i < array.size(); i++) {
bucketArr.get((array.get(i) - min) / bucketSize).add(array.get(i));
}
for (int i = 0; i < bucketCount; i++) {
if (bucketSize == 1) { // 如果带排序数组中有重复数字时
for (int j = 0; j < bucketArr.get(i).size(); j++)
resultArr.add(bucketArr.get(i).get(j));
} else {
if (bucketCount == 1)
bucketSize--;
ArrayList<Integer> temp = BucketSort(bucketArr.get(i), bucketSize);
for (int j = 0; j < temp.size(); j++)
resultArr.add(temp.get(j));
}
}
return resultArr;
}
(十)基数排序-是按照低位先排序,然后收集;再按照高位排序,然后再收集;依次类推,直到最高位。
1-实现步骤
步骤1:取得数组中的最大数,并取得位数;
步骤2:arr为原始数组,从最低位开始取每个位组成radix数组;
步骤3:对radix进行计数排序(利用计数排序适用于小范围数的特点);
2-算法分析
最佳情况:T(n) = O(n * k)
最差情况:T(n) = O(n * k)
平均情况:T(n) = O(n * k)
3-算法实现(java)
public static int[] RadixSort(int[] array) {
if (array == null || array.length < 2)
return array;
// 1.先算出最大数的位数;
int max = array[0];
for (int i = 1; i < array.length; i++) {
max = Math.max(max, array[i]);
}
int maxDigit = 0;
while (max != 0) {
max /= 10;
maxDigit++;
}
int mod = 10, div = 1;
ArrayList<ArrayList<Integer>> bucketList = new ArrayList<ArrayList<Integer>>();
for (int i = 0; i < 10; i++)
bucketList.add(new ArrayList<Integer>());
for (int i = 0; i < maxDigit; i++, mod *= 10, div *= 10) {
for (int j = 0; j < array.length; j++) {
int num = (array[j] % mod) / div;
bucketList.get(num).add(array[j]);
}
int index = 0;
for (int j = 0; j < bucketList.size(); j++) {
for (int k = 0; k < bucketList.get(j).size(); k++)
array[index++] = bucketList.get(j).get(k);
bucketList.get(j).clear();
}
}
return array;
}
好了,十大排序算法今天就介绍到这了,see you
参考资料