请补全JavaScript代码，要求将数组参数中的数字从小到大进行排序并返回该数组。
注意：
1. 数组元素仅包含数字
2. 请优先使用快速排序方法
[编程题]快速排序
<script>
function sort(arr,begin,end){
if(begin < end){
let i = begin;
let j = end;
let empty = arr[begin];
while(i < j){
while(arr[j] > empty && i < j){
j --;
}
arr[i] = arr[j];
while(arr[i] < empty && i < j){
i ++;
}
arr[j] = arr[i];
}
arr[i] = empty;
sort(arr,begin,i-1);
sort(arr,i+1,end);
}else{
return;
}
}
let arr = [2,3,1,4,8,7,9,6];
sort(arr,0,7);
console.log(arr);
</script>
发表于 2022-08-17 10:09:35
回复(0)
快排递归版
首先要知道递归的三大要素
1：结束条件 （没有结束条件必然栈溢出）
2：函数目的
3：等价关系 （在函数中怎么调用函数本身 要知道调用函数本身的目的才能明白）
const _quickSort = array => {
// 补全代码
//第一要素 结束条件 定义返回条件 如果数组的长度小于1 那么就返回就行了
if(array.length<=1){
return array
}
//第二要素 函数目的 寻找比中间数小的放做数组 大的放右数组
//先将找到数组的中间位置的下标
let mid = Math.floor(array.length/2);
//在元素数组中删除这个元素。 并保存这个数
var midNumber = array.splice(mid,1)[0];
//定义比中间位置数值小的数组 （比数组中间位置元素小的放在leftArr）
let leftArr = []
//定义比中间位置数值小的数组 （数组中间位置元素大的放在rightArr）
let rightArr = []
for(let i = 0 ; i<array.length; i++){
if(midNumber>array[i]){
leftArr.push(array[i])
}else{
rightArr.push(array[i])
}
}
//第三要素 等价关系
//左边leftArr midNumber rightArr 将这三个数组链接起来。midNumber是这一个数
let leftSort= _quickSort(leftArr)
let midSort = [midNumber]
let rightSort = _quickSort(rightArr)
return leftSort.concat(midSort,rightSort)
//return _quickSort(leftArr).concat([midNumber],_quickSort(rightArr))
}
发表于 2021-12-01 20:11:37
回复(0)
<!DOCTYPE html>
<html>
<head>
<meta charset=utf-8>
</head>
<body>
<script type="text/javascript">
const _quickSort = array => {
if(array.length <= 1) return array
// 补全代码
let pivotIndex = Math.floor(array.length / 2)
let pivot = array.splice(pivotIndex,1)[0]
let left = []
let right = []
for(let i = 0; i < array.length; i++) {
if(array[i] < pivot) {
left.push(array[i])
} else if(array[i] >= pivot) {
right.push(array[i])
}
}
return _quickSort(left).concat([pivot],_quickSort(right))
}
</script>
</body>
</html>
发表于 2022-08-19 00:05:01
回复(0)
<script>
const _quickSort = (array) => {
// return array.sort()
if(array.length <= 1) {
return array;
}
let left = []
let right = []
let middle = array[0]
for(let i = 0; i < array.length; i++){
if(array[i] < middle){
left.push(array[i])
}else if(array[i] > middle){
right.push(array[i])
}
}
left = _quickSort(left)
right = _quickSort(right)
left.push(middle)
return left.concat(right)
}
const result = _quickSort([0,-1,1,-2,2])
console.log(result)
</script>
发表于 2023-08-18 23:31:04
回复(0)
function quickSort(arr) {
if (arr.length <= 1) return arr;
const pivotIndex = Math.floor(arr.length / 2);
const pivot = arr[pivotIndex];
const left = [];
const right = [];
for (let i = 0; i < arr.length; i++) {
if (i === pivotIndex) continue;
if (arr[i] < pivot) {
left.push(arr[i]);
} else {
right.push(arr[i]);
}
}
return quickSort(left).concat(pivot, quickSort(right));
}
if (arr.length <= 1) return arr;
const pivotIndex = Math.floor(arr.length / 2);
const pivot = arr[pivotIndex];
const left = [];
const right = [];
for (let i = 0; i < arr.length; i++) {
if (i === pivotIndex) continue;
if (arr[i] < pivot) {
left.push(arr[i]);
} else {
right.push(arr[i]);
}
}
return quickSort(left).concat(pivot, quickSort(right));
}
来自ChatGPT的代码
发表于 2023-02-23 14:43:25
回复(0)
// 补全代码
if(array.length <= 1) return array
let middleIndex = Math.floor(array.length /2)
let middle = array.splice(middleIndex,1)[0]
let left = []
let right = []
for(let i =0;i<array.length;i++) {
array[i] < middle ? left.push(array[i]) : right.push(array[i])
}
return [..._quickSort(left),middle,..._quickSort(right)]
发表于 2022-11-19 15:51:11
回复(0)
const _quickSort = array => {
// 补全代码 正经八百 快速排序 不让过是吧
if (array.length < 2) return array
const left = [], right = []
const mid = array.splice(Math.floor(array.length / 2), 1)[0]
for (let i = 0; i < array.length; i++) {
if (array[i] < mid) left.push(array[i])
else right.push(array[i])
}
return _quickSort(left).concat(mid, _quickSort(right))
}
发表于 2022-11-08 14:38:10
回复(0)
离谱，本地输出数组，这上面
通不过，输出null
<!DOCTYPE html>
<html>
<head>
<meta charset=utf-8>
</head>
<body>
<script type="text/javascript">
const _quickSort = array => {
// 补全代码
//使用快速排序: 先找一个比较顺序的标准，然后比他大的放后面，比他小放前面
//先定义一个单趟排序函数
function sglSort(arr){
if(arr.length==1){
return arr
}else{
//定义一个base
let base =parseInt(arr.length/2)
let key = base;
let baseNum = arr[base]
let left = 0;
let right = arr.length-1;
//取中间值为基准值
//left<right时就一直循环
while(left<right){
while(arr[left]<=baseNum &&left!=right){
left++;
}
//交换left与base的位置
arr[base] = arr[left]
base = left
while(arr[right]>=baseNum&&left!=right){
right--;
}
arr[base] = arr[right]
base = right
}
base = left
arr[base]=baseNum;
let leftArr = arr.splice(0,base)
let rightArr = arr.splice(1,)
//判断是否出现了空串
if(leftArr.length!=0&&rightArr.length!=0){
return [...sglSort(leftArr),baseNum,...sglSort(rightArr)];
}else if(leftArr.length==0&&rightArr.length!=0){
return [baseNum,...sglSort(rightArr)];
}else{
return [...sglSort(leftArr),baseNum];
}
}
}
return sglSort(array);
}
</script>
</body>
</html> 通不过，输出null
发表于 2022-10-29 10:34:32
回复(0)
if(array.length<=1)return array
let mid=Math.floor(array.length/2)
let midValue=array.splice(mid,1)[0]
let left=[],right=[]
for(let a of array){
a<midValue?left.push(a):right.push(a)
}
return _quickSort(left).concat(midValue,_quickSort(right))
发表于 2022-09-08 15:20:25
回复(0)
const _quickSort = array => {
// 补全代码
return array.sort()
}
发表于 2022-08-08 10:29:09
回复(0)
<!DOCTYPE html>
<html>
<head>
<meta charset="utf-8" />
</head>
<body>
<script type="text/javascript">
const _quickSort = (array) => {
// 补全代码
const sort = (arr, left, right) => {
if (arr.length == 1) {
return arr;
}
// 先取基础值
let baseval = arr[left];
let i = left,
j = right;
let mid = left;
// 先从右往左轮询一次
for (; j >= left; j--) {
// 如果右边的值小于左边的值,则将右边的值赋给左边
if (arr[j] < baseval) {
arr[i] = arr[j];
}
for (; i <= right; i++) {
if (arr[j] > baseval) {
break;
} else {
if (i == j) {
mid = j;
arr[j] = baseval;
break;
}
if (arr[i] > baseval) {
arr[j] = arr[i];
break;
}
}
}
// 如果两者相等,说明是在中间相遇,直接将基础值赋值
if (j == i) {
mid = j;
arr[j] = baseval;
break;
}
}
if (mid == left || mid == right) {
return arr;
} else {
if (mid - 1 >= left) sort(arr, left, mid - 1);
if (mid + 1 <= right) sort(arr, mid + 1, right);
return arr;
}
};
return sort(array, 0, array.length - 1);
};
</script>
</body>
</html>
发表于 2022-07-26 16:07:13
回复(0)
const _quickSort = array => {
// 补全代码
// 快速排序步骤：
// 1. 任意选择一个基准
// 2. 所有小于基准的元素一道基准的左边，大于基准的元素一道基准的右边
// 3. 对基准左边和右边的两个子集不断重复前两步，直到每个子集只剩下一个元素
if (array.length <= 1) {
return array;
}
// 获取每次基准点的索引值
const pivotIndex = Math.floor(array.length / 2);
const pivot = array.splice(pivotIndex, 1)[0];
let left = [];
let right = [];
for (var i = 0; i < array.length; i++) {
if (array[i] < pivot) {
left.push(array[i]);
} else {
right.push(array[i]);
}
}
left = _quickSort(left);
right = _quickSort(right);
return left.concat(pivot).concat(right);
}
发表于 2022-07-20 19:18:35
回复(1)
const _quickSort = array => {
// 补全代码
const newdata=[]
array.map((item)=>{
if(typeof item!=='number'){
return
}else{
newdata.push(item)
}
})
return newdata.sort((a,b)=>a-b)
}
// 补全代码
const newdata=[]
array.map((item)=>{
if(typeof item!=='number'){
return
}else{
newdata.push(item)
}
})
return newdata.sort((a,b)=>a-b)
}
发表于 2022-05-21 19:29:12
回复(0)
const _quickSort = array => {
// 补全代码
if(array.length <= 1 ) return array;
const left = [];
const right = [];
let pivot = array[0];
for(let i = 1; i<array.length;i++) {
if(pivot < array[i]) {
left.push(array[i])
} else {
right.push(array[i])
}
}
return [..._quickSort(left),pivot,..._quickSort(right)]
}
发表于 2022-04-18 22:13:09
回复(0)
const _quickSort = array => {
// 补全代码
var start=0;
var end=array.length-1;
var base = qSort(start,end,array);
qSort(start,base-1,array);
qSort(base+1,end,array);
return array;
}
function qSort(left,right,arr){
let pivot = arr[left];//0
while(left<right){
while(arr[right] > pivot && left < right)right--;
arr[left]=arr[right];
while(arr[left] < pivot && left <right)left++;
arr[right]=arr[left];
}
arr[left]=pivot;
return left;
}
发表于 2022-04-07 13:02:10
回复(0)
问题信息
难度：
31条回答
55收藏
778浏览
通过挑战的用户
查看代码-
2023-06-29 16:00:22
-
2023-06-29 15:22:27
-
2023-06-29 11:23:43
-
2023-06-27 17:59:08
-
2023-06-27 15:01:09
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K2座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
