JS常见排序算法

算法描述

最近看到一篇介绍排序算法的文章,自己在此学习总结一下。

1.由数组第一位数值开始与相邻数值进行比较,每次将比较后大的数值后移。最后将会把数组中最大值移动到数组最后;

金沙官网线上 1

2.依次对数组中未排序序列重复进行比较排序,将比较后的最大值移动到未排序序列的最后;

1-冒泡排序

金沙官网线上 2

算法思路

依次比较相邻2个数的大小,如果不符合要求则交换。这样第一轮循环结束,最大值或最小值排在数组最后一位。剩下的数值重复以上步骤,直到排序结束。

以对数组[3,2,5,1,4] 进行从小到大排序为例,步骤如下:

  1. 3和2比较,3大于2。交换位置,数组为[2,3,5,1,4]
  2. 3和5比较,3小于5。不交换位置,数组不变。
  3. 5和1比较,5大于1。交换位置,数组为[2,3,1,5,4]
  4. 5和4比较,5大于4。交换位置,数组为[2,3,1,4,5]

这样第一轮循环结束,最大值5排在数组最后一位。然后再对剩下的数值重复这个过程,这样下来每次循环都会排到一个正确的数值。直至剩下最后一个位置,所有排序结束。

 

代码实现

//交互数值函数
function swap(myArray, p1, p2){
    var temp = myArray[p1];
    myArray[p1] = myArray[p2];
    myArray[p2] = temp;
}

//冒泡排序
function bubbleSort(myArray) {
    var len = myArray.length,
        stop = 0;

    for(let i = 0; i < len - 1; i++){
        for(let j = 0,stop = len - 1 - i; j < stop; j++){
            if(myArray[j] > myArray[j+1]){
                swap(myArray, j, j + 1);
            }
        }
    }

    return myArray;

}

代码实现

2-选择排序

     /*
        例如:对数组:{ 5,4,3,2,1 }进行比较 

        第一轮:{ 4,3,2,1,5 } :共比较四次
        第二轮:{ 3,2,1,4,5 } :共比较三次
        第三轮:{ 2,1,3,4,5 } :共比较二次
        第四轮:{ 1,2,3,4,5 } :共比较一次
        */
        public void Bubble(int[] arr)
        {
            int temp;

            bool flag;

            for (int i = 0; i < arr.Length - 1; i++) // 循环轮数
            {
                flag = true;

                for (int j = 0; j < arr.Length - i - 1; j++) // 比较次数
                {
                    if (arr[j] > arr[j + 1])
                    {
                        temp = arr[j];
                        arr[j] = arr[j + 1];
                        arr[j + 1] = temp;
                        flag = false;
                    }
                }

                if (flag == true)
                {
                    break;
                }
            }

            Console.Write("冒泡排序:");
            foreach (int item in arr)
            {
                Console.Write(item + " ");
            }
        }

算法思路

金沙官网线上,选择排序与冒泡类似,也是相邻位2个数比较大小。不同的是当不符合要求时,不是立马交换位置,而是给当前数值标记来表明最小或最大值,并且当前的最小或最大值依次比较数组里的数值。等一轮结束,找出最小或最大值再交换位置,其余位置不变。剩余数值重复以上步骤,直到排序结束。

以对数组[3,2,5,1,4] 进行从小到大排序为例,步骤如下:

  1. 假设第一个位置的3为最小值。
  2. 最小值3和2比较,3大于2。那么2标记为最小值。
  3. 最小值2和5比较,2小于5。最小值标记不变。
  4. 最小值2和1比较,2小于1。那么1为最小值。
  5. 最小值1和4比较,1小于4。最小值标记不变。
  6. 一轮结束后,第一位置的3和第四位置的1交换位置,数组为[1,2,5,3,4]

第一轮结束后,最小值1排到正确位置。剩下数值重复上述步骤,直到排序结束。

 

代码实现

//选择排序
function selectionSort(myArray) {
    let len = myArray.length;

    for(let i = 0; i < len; i++){

        //假设当前位置为最小值
        let min = i;

        //遍历剩下数字是否为最小
        for(let j = i + 1; j < len; j++){
            if(myArray[j] < myArray[min]){
                min = j;
            }
        }

        //如果当前位置不是最小值,替换最小值
        if(i !== min){
            swap(myArray,i,min);
        }
    }

    return myArray;


}

完整代码

3-插入排序

本文由金沙官网线上发布于编程,转载请注明出处:JS常见排序算法

您可能还会对下面的文章感兴趣: