数据结构常见的八大排序算法 绝地灬酷狼 2022-05-10 00:03 158阅读 0赞 python实现代码 [https://www.cnblogs.com/hokky/p/8529042.html][https_www.cnblogs.com_hokky_p_8529042.html] 排序算法:内部排序 + 外部排序 内部排序:插入、选择、交换、归并、基数排序 插入排序:直接插入排序+希尔排序 选择排序:简单选择排序+堆排序 交换排序:冒泡排序+快速排序 //定义一个公用函数 function swap(myArray, p1, p2){ let temp = myArray[p1]; myArray[p1] = myArray[p2]; myArray[p2] = temp; } * **直接插入:**将数组中的所有元素依次跟前面已经排好的元素相比较,如果选择的元素比已排序的元素小,则交换,直到全部元素都进行比较。 function insertionSort(myArray) { const length = myArray.length; // 数组的长度 let value, // 当前比较的值 i, // 未排序部分的当前位置 j; // 已排序部分的当前位置 for (i=0; i < length; i++) { // 储存当前位置的值 value = myArray[i]; /* * 当已排序部分的当前元素大于value, * 就将当前元素向后移一位,再将前一位与value比较 */ for (j=i-1; j > -1 && myArray[j] > value; j--) { myArray[j+1] = myArray[j]; } myArray[j+1] = value; } return myArray; } * **希尔排序:**将待排序数组按照步长gap进行分组,然后将每组的元素利用直接插入排序的方法进行排序;每次将gap折半减小,循环上述操作;当gap=1时,利用直接插入,完成排序。 function shell(myArray) { const gap = Math.floor(myArray.length / 2); while(gap >= 1) { for(let i = 0;i < myArray.length;i++){ if(myArray[i] > myArray[i + gap]) swap(myArray, i, i+gap) } gap = Math.floor(gap / 2); } } * **简单选择排序:**从待排序序列中,找到关键字最小的元素;如果最小元素不是待排序序列的第一个元素,将其和第一个元素互换;从余下的 N - 1 个元素中,找出关键字最小的元素,重复(1)、(2)步,直到排序结束。 function selectionSort(myArray){ const length = myArray.length; for (let i=0; i < length; i++){ // 将当前位置设为最小值 let min = i; for (let j=i+1; j < length; j++){ if (myArray[j] < myArray[min]){ min = j; } } // 如果当前位置不是最小值,将其换为最小值 if (i != min){ swap(myArray, i, min); } } return myArray; } * **堆排序:**首先将序列构建成为大顶堆;取出大顶堆的根节点,将其与序列的最后一个元素进行交换;对交换后的n-1个序列进行调整使其成为大顶堆;重复以上步骤,直至序列中只有一个元素。 * **冒泡排序:**将序列当中的左右元素,依次比较,保证右边的元素始终大于左边的元素;( 第一轮结束后,序列最后一个元素一定是当前序列的最大值;)对序列当中剩下的n-1个元素再次执行步骤1。对于长度为n的序列,一共需要执行n-1轮比较(利用while循环可以减少执行次数) function bubbleSort(myArray){ const length = myArray.length; for (let i = 0; i < length - 1; i++){ for (let j = 0; j < length - 1 - i; j++){ if (myArray[j] > myArray[j + 1]){ swap(myArray, j, j + 1); } } } return myArray; } * **快速排序:**从序列当中选择一个基准数(pivot);将序列当中的所有数依次遍历,比基准数大的位于其右侧,比基准数小的位于其左侧;重复步骤1.2,直到所有子集当中只有一个元素为止。 var quickSort = function(arr) { if (arr.length <= 1) { return arr; } var pivotIndex = Math.floor(arr.length / 2); var pivot = arr.splice(pivotIndex, 1)[0]; var left = []; var right = []; for (var i = 0; i < arr.length; i++){ if (arr[i] < pivot) { left.push(arr[i]); } else { right.push(arr[i]); } } return quickSort(left).concat([pivot], quickSort(right)); }; * **归并排序:**先使每个子序列有序,再使子序列段间有序。归并排序其实要做两件事:分解——将序列每次折半拆分;合并——将划分后的序列段两两排序合并。 function merge(left, right){ let result = [], il = 0, ir = 0; while (il < left.length && ir < right.length){ if (left[il] < right[ir]){ result.push(left[il++]); } else { result.push(right[ir++]); } } return result.concat(left.slice(il)).concat(right.slice(ir)); } function mergeSort(myArray){ if (myArray.length < 2) { return myArray; } let middle = Math.floor(myArray.length / 2), left = myArray.slice(0, middle), right = myArray.slice(middle); return merge(mergeSort(left), mergeSort(right)); } * **基数排序:**通过序列中各个元素的值,对排序的n个元素进行若干趟的“分配”与“收集”来实现排序。 分配:我们将L\[i\]中的元素取出,首先确定其个位上的数字,根据该数字分配到与之序号相同的桶中; 收集:当序列中所有的元素都分配到对应的桶中,再按照顺序依次将桶中的元素收集形成新的一个待排序列L\[ \]; 对新形成的序列L\[\]重复执行分配和收集元素中的十位、百位...直到分配完该序列中的最高位,则排序结束; [https_www.cnblogs.com_hokky_p_8529042.html]: https://www.cnblogs.com/hokky/p/8529042.html
还没有评论,来说两句吧...