如何在单个循环中对数组进行排序？

Question

所以我正在经历不同的排序算法。但是几乎所有的排序算法都需要 2 个循环来对数组进行排序。冒泡排序和插入排序的时间复杂度在最佳情况下为 O(n)，在最坏情况下为 O(n^2)，再次需要 2 个循环。有没有办法在单个循环中对数组进行排序？

Answer 1

这里是 Python 中的单循环冒泡排序：

def bubbly_sortish(data):
    for _ in xrange(len(data)**2):
        i, j = _/len(data), _%len(data)
        if i<j and data[i] > data[j]:
            data[i], data[j] = data[j], data[i]

A = [5, 1, 2, 3, 5, 6, 10]
bubbly_sortish(A)

print A

当然这是个玩笑。但这表明循环次数与算法复杂度关系不大。

现在，如果您问是否可以使用 O(n) 比较对数组进行排序，不，这是不可能的。对于基于比较的排序算法，下界是 Ω(n log n)。

Answer 2

int list[] = { 45, 78, 22, 96, 10, 87, 68, 2 };
    for (int i = 1; i < list.length; i++) {
        if (list[i] < list[i - 1]) {
            list[i] = list[i] + list[i - 1];
            list[i - 1] = list[i] - list[i - 1];
            list[i] = list[i] - list[i - 1];
            i = 0;
        }
    }
    System.out.print("Sorted array is : ");
    for (int i = 0; i < list.length; i++) {
        System.out.print(list[i] + " ");
    }

Answer 3

使用 C++ 的单循环冒泡排序

int a[7]={5,7,6,2,4,3,1};

int temp = 0;

int j = 0;

for(int i = 0 ; i<a[]-1 ; i++)
{
    int flag = 0;
    if(a[i]>a[i+1])
    {
        temp = a[i];
        a[i] = a[i+1];
        a[i+1] = temp;
        flag = 1;
    }       
    if(i == 7-2-j)
    {
        if(!flag) break;
        i = -1;
        j++;
    }
}

Answer 4

在一般情况下，您的平均值为 O(n lg n)。

但在特定情况下，最好的情况是 O(n)，我认为它足够接近您所说的“只有一个循环”，即使实现可能显示

for

关键字的多个实例。好消息是，您不是靠运气来实现最佳案例。如果您知道有关数据的一些属性，则可以选择一些特定的算法。例如：

3-way quicksort 运行非常接近 O(n) 当你有很多项目只有几个不同的排序键（将服务器日志条目视为项目和日期作为键）。
如果您的键很容易索引（如字符集或小整数），并且索引具有已知的上限 k，则计数排序在 O(n+k) 中运行。
Burstsort 将在 O(wn) 中运行，如果你正在处理最大长度 w 的字符串。

这只是三个例子。对于许多类型的受限数据集，还有更多，太多了，无法从我的脑海中回忆起来。如果您手头有一个 O(n lg n) 不够好的真实案例，那么值得进行一些适当的研究，前提是您在数据中确定了一些有趣的属性。

Answer 5

javascript:
function bruteForce(arr){
    for(var i=0;i<arr.length; ){
        if(arr[i+1]< arr[i]){
            var temp = arr[i];
            arr[i]=arr[i+1];
            arr[i+1] = temp;
            i--;
            if(i === -1) i=0;
        }else i++;
    }

    return  arr;
 }

alert(bruteForce([2,3,4,5,6,23,1,1]));

复制代码并粘贴到浏览器的 URL 中，然后按回车键。如果错过了

javascript:

，请添加它。

Answer 6

这里是仅使用单循环对数组进行排序的代码。

var array = [100, 110, 111, 1, 3, 19, 1, 11, -10]
var i = 1

while i < array.count - 1 {
    if array[i] > array[i + 1] {
        let temp = array[i];
        array[i] = array[i + 1];
        array[i + 1] = temp;
        i = -1;
    }
    i = i + 1;
}
print(array)

Answer 7

这是您给定示例的工作版本：

如果您知道要排序的值的范围，那么解决问题的一种非常快速高效且合乎逻辑的方法是可行的，例如

0 <= val <= 100

其中 val 是整数。

然后你可以在两个循环中通过单个读写操作来完成......一个用于读取数组，一个用于写入它排序：

使用第二个数组，其中索引代表值 0-100，将遇到每个值 0-100 的次数存储在其中，例如

val = 100

可能在目标数组中存在 234 次...

只有一个读循环和一个写循环，这在计算上和一个循环同时读和写一样高效，而且比使用比较的循环更快......如果你坚持，你可以做到在单个循环中，目标数组长度的两倍，并在新数组写入操作中将 i 值重置为零。

第二个循环简单地按顺序写入第一个数组中遇到的每个值的计数。

Answer 8

单循环数组排序：

for(int i = 0, j=i+1; i < arr.length && j<arr.length;)
    {       
        if(arr[i] > arr[j])
        {
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;              
            i=0;
            j=i+1;
        } 
        else
        {
            i++;
            j++;
        }
    }

Answer 9

public void sortArrayUsingSingleLoop(int[] intArray) {
        int temp;
        boolean swap = false;
        for(int i=0;i<intArray.length-1;i++){
         if(intArray[i]>intArray[i+1]){
             temp=intArray[i];
             intArray[i]=intArray[i+1];
             intArray[i+1]=temp;
             swap=true;
         }

         if(swap &&i==intArray.length-2){
            i=-1;swap=false;
         }
        }

    }

Answer 10

以下代码在php中。你可以在https://paiza.io/projects/4pAp6CuB-e9vhGIblDNCZQ.

上测试代码

  $a = [8,3,4,9,1];
    for($i=0;$i<count($a)-1;$i++){
        if($a[$i] > $a[$i+1]){
            $temp = $a[$i];
            $a[$i] = $a[$i+1];
            $a[$i+1] = $temp;
            $i = -1;
        }
    }
    print_r($a);

Answer 11

公共课 SinleLoopeSorting {

public static void main(String[] args) {
    Integer[] x = new Integer[] { 1, 7, 8, 0, 4, 2, 3 };

    for (int i = 0; i < x.length - 1; i++) {
        if (x[i] > x[i + 1]) {
            int p = x[i];
            x[i] = x[i + 1];
            x[i + 1] = p;
            i = -1;
        }
    }
    for (int i = 0; i < x.length; i++) {
        System.out.println(x[i]);
    }
}

}

Answer 12

这可用于使用单个循环对数组进行排序：- 注意事项：

将 i 的值更新为 -1，使其在 i++ 之后始终从 0 开始
减少数组的长度（大小--），因为最大值元素在每次循环完成时都在末尾结束

代码：

void sort(int *arr,int size){
    int i;
    for (i = 0; i <size; i++){
        if(arr[i]>arr[i+1]){
            arr[i]=arr[i]+arr[i+1];
            arr[i+1]=arr[i]-arr[i+1];
            arr[i]=arr[i]-arr[i+1];
            if(i==size-2){
                printf("%s\n","inside if loop" );
                i=-1;
                size--;
            }
        }
    }
}

Answer 13

def my_sort(num_list):
    x = 0
    while x < len(num_list) - 1:
        if num_list[x] > num_list[x+1]:
            num_list[x], num_list[x+1] = num_list[x+1], num_list[x]
            x = -1
        x += 1
    return num_list

print(my_sort(num_list=[14, 46, 43, 27, 57, 42, 45, 21, 70]))
#output [14, 21, 27, 42, 43, 45, 46, 57, 70]

Answer 14

单

for

插入排序循环：

强文字

function insertionSort (array) {
    for(var i = 1 ; i < array.length ;){
        if(array[1] < array[0]) {
                temp = array[i];
                array[i] = array[i -1];
                array[i -1] = temp; 
         }
        if(array[i] < array[i-1]){
            var temp = array[i]
            array[i] = array[i -1]
            array[i -1] = temp
            i--
        } else{i++}
    }
    return array
}

Answer 15

使用单循环（javascript）对数组进行排序

var arr = [4,5,2,10,3,7,11,5,1];
for(var i = 1; i < arr.length; i++)
{       
    if(arr[i] < arr[i-1])
    {
        arr[i] = arr[i] + arr[i-1];
        arr[i-1] = arr[i] - arr[i-1]; 
        arr[i] = arr[i] - arr[i-1];              
        i=0;
    } 
}

输出：arr = [1, 2, 3, 4, 5, 5, 7, 10, 11]

Answer 16

以下代码是用 PHP 对数组进行排序的最佳情况。 https://paiza.io/projects/r22X0VuHvPQ236jgkataxg

<?php
function quicksort($a){
    $n = count($a);
    $lt = [];
    $gt = [];

    if($n < 2){
       return $a;
    }else{
        $f = $a[0];
    }

    for($i = 1;$i < $n ;$i++){
        if($a[$i] > $f){
            $gt [] = $a[$i];
        }else{
            $lt [] = $a[$i];
        }
    }

    return array_merge(quicksort($lt),array($f),quicksort($gt));
}


$ar = [7,4,3,6,5,1,2];
echo "Input array => ".implode(' , ',$ar).'<br>';
$a = quicksort($ar);

echo "Output array => ".implode(' , ',$a);;

?>

Answer 17

在单循环中使用 java 对数组进行排序：

    public int[] getSortedArrayInOneLoop(int[] arr) {

    int temp;
    int j;

        for (int i = 1; i < arr.length; i++) {
        j = i - 1;

            if (arr[i] < arr[j]) {

            temp = arr[j];
            arr[j] = arr[i];
            arr[i] = temp;
            i = 1;

            }

        }

    return arr;

    }

Answer 18

晚会但希望这有帮助

java解决方案

for(int i=1;i< arr.length;i++) {
        if(arr[i] < arr[i-1] ){
            arr[i-1] += arr[i];
            arr[i] = arr[i-1] - arr[i];
            arr[i-1] -= arr[i];
            i=0;
        }
}

Answer 19

用蟒蛇：

def sort(array):
    n = len(array);
    i = 0;
    mod = 0;
    if(len(array)<= 1):
        return(array)

    while n-1:
        if array[mod] > array[mod+1]:
            array[mod], array[mod+1] = array[mod+1], array[mod]

        mod+=1
        if mod+1 >= n:
            n-=1
            mod = 0

    return array

Answer 20

    #include<stdio.h>

    void sort(int a[],int n,int k,int w)
    {   
      int i,j,z,key;
      n=n-1;
      j = k+1;
      key = a[j];
      i = j-1;
      while(i>0 && a[i]>key)
      {
        a[i+1] = a[i];
        i = i-1;
      }
      a[i+1] = key;
      k = k + 1;
      if(n!=0)
      {
       sort(a,n,k,w);
      }
    }

  int main()
 {
    int i,n,w,k=1,z=5,g;
    printf("enter the size of an array\n");
    scanf("%d",&n);
    g=n;
    int a[n];
    for(i=1;i<=n;i++)
    {
        scanf("%d", &a[i]);
    }
    w = n;
    sort(a,n-1,k,w);

    for(i = 1; i <= n; i++)
    {
        printf("%d", a[i]);
    }
 }

这里是解决方案。这可能对你有帮助。

Answer 21

public int find2ndLargest() {
    int[] arr = {1,3,14,25,7,20,11,30};
    int temp;

    // sort array
    for (int i=0;i<arr.length-1;i++) {
        if (arr[i]>arr[i+1]) {
            temp = arr[i];
            arr[i]=arr[i+1];
            arr[i+1]=temp;
            i=0;
        }
    }
    return arr[arr.length-2];
}

Answer 22

static int[] sort(int[] arr){
        int idx = 0;
        int len = arr.length - 1;
        int counter = len;
        while(true){
            if(idx != len && arr[idx] > arr[idx+1]){
                swap(arr, idx, idx + 1);
                counter--;
            }
            idx++;
            if(counter == len && idx == len){
                break;
            }
            if(idx == len){
                idx = 0;
                counter = len;
            }
        }
        return arr;
    }


    void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

Answer 23

就这么简单，请简单的步骤

         var arr=[5,1,4,3];
             for(var i=0;i<arr.length-1;i++){
                 var num=arr[i];
                 var num2=arr[i+1];
                //Check if first index value with next index value
                if(num>num2){
                  var temp=arr[i];
                  arr[i]=arr[i+1];
                  arr[i+1]=temp;
                  //assign i=0 to re start the loop to check the index value
                  i=0;
                 }
             }

控制台日志（arr）

Answer 24

您可以使用 while 循环并使用索引

       int i=0;
       int a[]={1,2,3,4,7,3};
       while(i<a.length)
       {
           if((i+1<a.length && a[i]>a[i+1]) )
           {
                swap(i,i+1,a);
               i=i-1;
           }
         if(i-1>=0 && a[i]<a[i-1] )
             {
             swap(i,i-1,a);
            i=i-1;
             }
           else
               i++;
       }

Answer 25

快速代码

func sortingOneArray(array: [Int]) -> [Int] {
    var sortedArray = array
    var i = 0
    while (i < sortedArray.count - 1) {
        if sortedArray[i] > sortedArray[i+1] {
            let temp = sortedArray[i]
            sortedArray[i] = sortedArray[i+1]
            sortedArray[i+1] = temp
            print("i \(i)")
            i = 0
        } else {
            i = i + 1
        }
    }
    return sortedArray
}

print(sortingOneArray(array: [1,3,7,4,2,0]))

如何在单个循环中对数组进行排序？

问题描述投票：0回答：25

25个回答

最新问题

如何在单个循环中对数组进行排序？

问题描述 投票：0回答：25

25个回答

最新问题

问题描述投票：0回答：25