InsertionSort مقابلInsertionSort مقابلBinaryInsertionSort

Question

لدي بضعة أسئلة بخصوص تطبيقات مختلفة من نوع الإدراج.

تنفيذ 1:

public static void insertionSort(int[] a) {
    for (int i = 1; i < a.length; ++i) {
        int key = a[i];
        int j   = i - 1;

        while (j >= 0 && a[j] > key) {
            a[j + 1] = a[j];
            --j;
        }

        a[j + 1] = key;
    }
}

تنفيذ 2:

public static void insertionSort(int[] a) {
    for (int i = 1; i < a.length; ++i) {
        for (int j = i; j > 0 && a[j - 1] > a[j]; --j) {
            swap(a, j, j - 1);
        }
    }
}

private static void swap(int[] a, int i, int j) {
    int tmp = a[i];

    a[i] = a[j];
    a[j] = tmp;
}

وهنا سؤالي الأول:ينبغي للمرء أن يفكر أن النسخة الأولى يجب أن تكون أسرع قليلا أن النسخة الثانية (لأن من أقل الواجبات) ولكن ليس (أو على الأقل الفرق انها لا تذكر).ولكن لماذا ؟

ثانيا, كنت أتساءل أن جافا المصفوفات.نوع الأسلوب() كما يستخدم النهج الثاني (ربما بسبب إعادة استخدام التعليمات البرمجية لأن مبادلة الطريقة المستخدمة في أماكن مختلفة, ربما لأنه من الأسهل أن نفهم).

تنفيذ 3 (binaryInsertionSort):

    public static void binaryInsertionSort(int[] a) {
    for (int i = 1; i < a.length; ++i) {
        int pos            = Arrays.binarySearch(a, 0, i, a[i]);
        int insertionPoint = (pos >= 0) ? pos : -pos - 1;

        if (insertionPoint < i) {
            int key = a[i];

            // for (int j = i; i > insertionPoint; --i) {
            //     a[j] = a[j - 1];
            // }
            System.arraycopy(a, insertionPoint, a, insertionPoint + 1, i - insertionPoint);

            a[insertionPoint] = key;
        }
    }
}

هو ثنائي نوع الإدراج من الناحية العملية ، أو هو أكثر من النظري الشيء ؟ على الصغيرة المصفوفات ، مناهج أخرى هي أسرع بكثير ، على أكبر المصفوفات mergesort/فرز سريع وأداء أفضل بكثير.

Answer 1

1. حذف الادعاء الكاذب
2. عدد من المقارنات في الأولين هو 1/2*n(n-1) ، باستثناء تلك المتعلقة الخارجي الحلقات.
3. أيا من هذه البرامج معنى كبير للعمل الحقيقي لأنها تقف, لأنهم لا الاستفادة من المعلومات المتاحة لهم.على سبيل المثال, فإنه من السهل لإضافة شيك الحلقة الداخلية لمعرفة ما إذا كان أي مقايضة تمت:إن لم يكن ثم فرز مجموعة ، ويمكن الانتهاء ، وربما إنقاذ أكثر من عمل.في ممارسة هذه الأنواع من النظر يمكن أن تسيطر على متوسط الحال.

حاشية وغاب السؤال عن جافا:أنا أفهم أن جافا نوعا ما جدا خوارزمية معقدة ، الذي يستخدم الكثير من الحالات الخاصة مثل متخصصة لفرز الحالات الصغيرة المصفوفات باستخدام فرز سريع إلى القيام رفع الأحمال الثقيلة.