标签: bubble-sort

在课堂上我们正在做排序算法,虽然我在谈论它们和编写伪代码时理解它们很好,但我在编写实际代码时遇到了问题.

这是我在Python中的尝试:

mylist = [12, 5, 13, 8, 9, 65]

def bubble(badList):
    length = len(badList) - 1
    unsorted = True

    while unsorted:
        for element in range(0,length):
            unsorted = False
            if badList[element] > badList[element + 1]:
                hold = badList[element + 1]
                badList[element + 1] = badList[element]
                badList[element] = hold
                print badList
            else:
                unsorted = True

print bubble(mylist)

现在,这(据我所知)正确排序,但一旦完成它就会无限循环.

如何修复此代码以使函数正确完成并正确排序任何(合理)大小的列表？

PS我知道我不应该在函数中真正打印,我应该有一个返回,但我还没有这样做,因为我的代码还没有真正起作用.

泡泡种类有任何现实世界的用途吗？每当我看到一个提到的,它总是要么:

1. 用于学习的排序算法.
2. 不使用排序算法的示例.

修复正整数n和k.

让A是长度的阵列n与A[i]长度的阵列k,其中每一个条目是n-i.例如,有n=5和k=1,这只是

[ [5] , [4] , [3] , [2] , [1] ]

而对于n=5和k=2,这是

[ [5,5] , [4,4] , [3,3] , [2,2] , [1,1] ]

目标是通过交换相邻数组中的数字(例如交换)来对这个数组数组进行冒泡排序A[i][j1],A[i+1][j2]直到每个数据A[i]都i+1为每个数组i.

问题是:需要多少交换以及什么是最佳算法？

注意: 有许多更好的排序算法可供使用.但是,对于这个问题,我只对应用如上所述的冒泡排序感兴趣.我只能交换相邻数组中的条目,我只对所需的最小数量的交换感兴趣.我很欣赏其他排序算法的所有建议,但这是我试图理解的问题.

例子:

因为k=1,这是众所周知的.交换次数是A被视为置换的反转次数,因此最小交换次数是二项式系数(n choose 2) = n(n-1)/2,这可以通过交换任何乱序对来实现:A[i] > A[j] …

int[] arr = {800,11,50,771,649,770,240, 9};

int temp = 0;

for (int write = 0; write < arr.Length; write++)
{
    for (int sort = 0; sort < arr.Length - 1; sort++)
    {
        if (arr[sort] > arr[sort + 1])
        {
            temp = arr[sort + 1];
            arr[sort + 1] = arr[sort];
            arr[sort] = temp;
        }       
    }   
    Console.Write("{0} ", arr[write]);  
}

我试图做的就是使用这个数组进行简单的冒泡排序.我想弄清楚为什么排序搞砸了.例如,这里的数组是{800,11,50,771,649,770,240, 9}:

以下是显示的内容: 11, 50, 649, 9, 649, 770, 771, 800

我想我可能会在比较中遗漏一些东西.

int currentMinIndex = 0;

for (int front = 0; front < intArray.length; front++)
{
    currentMinIndex = front;

    for (int i = front; i < intArray.length; i++)
    {
        if (intArray[i] < intArray[currentMinIndex])
        {
            currentMinIndex = i;
        }
    }

    int tmp = intArray[front];
    intArray[front] = intArray[currentMinIndex];
    intArray[currentMinIndex] = tmp;
}

内循环迭代:n +(n-1)+(n-2)+(n-3)+ ... + 1次.

外循环迭代:n次.

所以你得到n*(数字1到n的总和)

不是n*(n*(n + 1)/ 2)= n*((n ^ 2)+ n/2)

哪个是(n ^ 3)+(n ^ 2)/ 2 = O(n ^ 3)？

我很肯定我做错了.为什么不是O(n ^ 3)？

我很难解决这个问题,需要一种客户名称,客户ID,最后是应付金额.我有整个程序,但无法弄清楚进行排序所需的最后一个原型.我有一个名为Customers的结构,我也将提供int main()部分.我只需要任何帮助来启动原型SortData().

struct Customers {
    string Name;
    string Id;
    float OrderAmount;
    float Tax;
    float AmountDue;
};

const int MAX_CUSTOMERS = 1000;
bool MoreCustomers(int);
Customers GetCustomerData();
void OutputResults(Customers [], int);
void SortData(const int, const int, Customers []);

int main() {
    Customers c[MAX_CUSTOMERS]; 
    int Count = 0;      
    do {
      c[Count++] = GetCustomerData();   
    } while (MoreCustomers(Count));     


    for (int i = 0; i < Count; i++) {
        c[i].Tax = 0.05f * c[i].OrderAmount;        
        c[i].AmountDue = c[i].OrderAmount + c[i].Tax;   
    }

    SortData(0, Count, c);     //0:Sorts by customer …

我编写了一个冒泡排序算法来对链表进行排序.我是Java初学者并且正在尝试学习数据结构.我很困惑为什么我的第二个元素没有正确排序.

编辑

class SListNode {
  Object item;
  SListNode next;


  SListNode(Object obj) {
    item = obj;
    next = null;
  }


  SListNode(Object obj, SListNode next) {
    item = obj;
    this.next = next;
  }

}
public class SList {

    private SListNode head;
    private SListNode temp;

    public void sortList() {
        SListNode node = head,i,j;
        head = node;
        i = node;
        j = node.next;
        while(i.next != null) {
            while(j.next != null) {
                if((Integer)i.item < (Integer)j.item) {
                    temp = i.next;
                    i.next = j.next;
                    j.next = temp; …

我需要在PHP中进行冒泡排序算法.

我想知道是否有任何一个我可以使用的好例子,或者是一个可以做到这一点的开源库.

我在一个集合(数组)中有一些空格,我想用对象(一个人)填充这些空间,所以没有空间可以有男性和女性,这就是为什么我试图找出一个冒泡排序算法.

我的计划是填写任何可用的空间,无论性别如何,然后分别对它们进行排序.

谢谢.

我将为学生实现一个玩具磁带"大型机",显示"快速排序"类功能的快速性(递归与否,由于硬件速度慢,并且众所周知的堆栈反转技术并不重要) "bubblesort"函数类.因此,虽然我清楚硬件实现和控制器,但我猜测,快速排序功能在顺序,顺序和比较距离方面要比其他功能快得多(从中间回放磁带要快得多)结束,因为倒带速度不同).

不幸的是,事实并非如此; 这个简单的"气泡"代码在比较距离,方向和比较和写入次数方面与"快速排序"功能相比显示出很大的改进.

所以我有3个问题:

1. 我实施快速排序功能时是否有错？
2. 我在实现bubblesoft功能时遇到了错误吗？
3. 如果没有,为什么"bubblesort"在(比较和写入操作)中的功能比"quicksort"功能快得多？

我已经有了"quicksort"功能:

void quicksort(float *a, long l, long r, const compare_function& compare)
{
    long i=l, j=r, temp, m=(l+r)/2;
    if (l == r) return;
    if (l == r-1)
    {
        if (compare(a, l, r))
        {
            swap(a, l, r);
        }
        return;
    }
    if (l < r-1)
    {
        while (1)
        {
            i = l;
            j = r;
            while (i < m && !compare(a, i, m)) i++;
            while (m < j && !compare(a, m, j)) j--;
            if (i …

我想知道如何优化冒泡排序,以便它忽略已经排序的元素,即使在第一次传递之后.

Eg. [4, 2, 3, 1, 5, 6] --> [2, 3, 1, **4, 5, 6**]

我们观察到[4,5,6]已经按排序顺序,如何修改我的代码以便它在下一遍中忽略这3个元素？(这意味着排序会更有效？)你建议使用递归方法吗？

public static void bubblesort(int[] a) {
  for(int i=1; i<a.length; i++) {
    boolean is_sorted = true;

    for(int j=0; j<a.length; j++) {
      if(a[j] > a[j+1]) {
         int temp = a[j];
         a[j] = a[j+1];
         a[j+1] = temp;
         is_sorted = false;
      }
    }

    if(is_sorted) return;
  }
}

谢谢你的时间!