Сортировка массива вручную в порядке возрастания

Question

У меня есть домашнее задание для сортировки массива в порядке возрастания. Очевидно, что это должно быть сделано вручную без использования какой-либо функции sort().

Я решил сделать это, мне понадобятся два цикла for: первый будет проходить через существующий массив и создавать временное значение со значением и индексом массива. Второй цикл будет сравнивать временные значения с существующими значениями и сортировать их. Я продолжаю пытаться написать код, но просто не могу понять, как это правильно. Вот последний метод, который я придумал:

public int[] sortArray (int[] inArray)
{
    //Construct the array we're using here
    int[] newArray = inArray;

    for(int x = 0; x < a.length; x++) //a.length = # of indices in the array
    {
        int tempValue = a[x];
        int tempIndex = x;

        for(int y = 0; y < a.length; y++)
        {
            if(tempValue < a[y])
            {
                newArray[x] = tempValue;
            }
        }
    }

    return newArray;
}

Я почти уверен, что это неправильно, но если бы кто-то мог подтолкнуть меня в правильном направлении, это было бы очень признательно!

Answer 1

У вас есть почти нормальная версия Выбор сортировщика . Вам нужно начать y с x+1, а не с 0. В противном случае вы повторно сканируете отсортированную часть массива. Следует также отметить, что сортировка выбора является алгоритмом на месте; если вы хотите сделать копию массива, вам следует использовать метод Arrays.copy, в противном случае int[] newArray = inArray; создает псевдоним, а не копию. Наконец, оператор if во вложенном цикле должен swap a[x] и a[y], а не просто вставлять tempValue в:

if(newArray[x] < newArray [y]) {
    int tempValue = newArray[y];
    newArray[y] = newArray[x];
    newArray[x] = tempValue;
}

Answer 2

int minval = input[0];
int temp=0;


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

Answer 3

Сортировка, которую вы пытаетесь достичь, называется Bubble sort - запись в википедии довольно хороша, вы должны ее прочитать. Тем не менее, он никогда не используется, потому что есть лучшая альтернатива - сортировка вставок (например, Timsort в Python, который является гибридом сортировки слиянием и сортировки вставкой). Эти два основных алгоритма, которые соответствуют вашей идее с двумя циклами, следовательно, сложность O (n ² ).

Вам также следует рассмотреть различные алгоритмы для вашего задания или, по крайней мере, знать:

• Сортировка слиянием
• Quicksort

Надеюсь, это поможет.

Answer 4

Вместо того, чтобы пытаться придумать свой собственный алгоритм сортировки, я призываю вас изучить то, что уже существует. На этом уровне тонна предшествующего уровня техники.

Взгляните на статью в Википедии: Алгоритм сортировки .

Пузырьковая сортировка очень проста в реализации, но имеет квадратичную сложность (такая же, как ваша текущая попытка).

Быстрая сортировка не слишком сложна для реализации и имеет лучшую среднюю сложность.

Answer 5

int[] number = { 1,2,1,3,5,4 };
    int temp;
     for (int i = 0; i < number.length; i++)
        {
            for (int j = i + 1; j < number.length; j++)
            {
                if (number[i] > number[j])
                {
                    temp =  number[i];
                    number[i] = number[j];
                    number[j] = temp;
                }
            }
        }

        for (int i = 0; i <number.length; ++i)
            System.out.println(number[i]);
    }

Answer 6

int arr[] = new int[]{10, 20, 5, 6, 30, 1, 2};
    boolean bool = true;
    int t = 0;
    while (bool) {
        for (int i = 0; i < arr.length - 1; i++) {
            if (arr[i] > arr[i + 1]) {
                int c = arr[i];

                arr[i] = arr[i + 1];
                arr[i + 1] = c;
                t++;
            }
        }
        if (t == 0) {
            bool = false;
        }
        t = 0;
    }

    for (int y : arr) {
        System.out.println(y);
    }

Answer 7

создание нового массива определенно не нужно, а не то, что вы должны делать.

Чтобы узнать, как отсортировать список, ознакомьтесь с предложениями Google:

https://www.google.com/webhp?sourceid=chrome-instant&ix=sea&ie=UTF-8&ion=1#hl=en&output=search&sclient=psy-ab&q=computer%20science%20list%20sorting&oq=&aq=&aqi=&aql=&gs_l=&pbx=1&fp=bda1eff6cc14f834&ix=sea&ion=1&bav=on.2,or.r_gc.r_pw.r_cp.r_qf.,cf.osb&biw=1215&bih=679